Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem

Full text

Pdf (705 KB)

Source

Journal of the ACM (JACM) archive
Volume 30 , Issue 1 (January 1983) table of contents

Pages: 118 - 132

Year of Publication: 1983

ISSN:0004-5411

Author

Bezalel Gavish

Graduate School of Management, University of Rochester, Rochester, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 46, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322358.322367 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BENDERS J.F Partmomng procedures for solving mixed-variables programming problems Numer. ische Math. 4 (1962), 238-252.
	2	Chandy, K.M, ANI) Lo, T. The capacttated muumum spanning tree. Networks 3, 2 (1973), 173-182.
	3	DArnTZIG, G.B., AND WOLFE, PThe decomposition algorithm for linear programming. Econometrica 29, 4 (1961), 10t-111.
	4	DIJKSTRA, E W. A note on two problems m connection with graphs. Numerische Math. 1 (1959), 269-271
	5	ELIAS, D., AND FERGUSON, M J Topological design of mulUpoint teleprocessmg networks IEEE Trans. Commun. COM-22 (197#), 1753-1762.
	6	ESSAU, L.R., AND WILLXA~S, K C.On teleprocessmg system design, IBM Syst J 5, 3 (1966), 142-147.
	7	Fisher, M.L.The Langrangian relaxation method for solving integer programming problems. Manage Sci. 27, 1 (1981), 1-18.
	8	GABOW, H.N A good algorithm for smallest spanning trees wtth a degree constraint. Networks 8 (1978), 201-208.
	9	GAVlSR, B.New algorithms for the capacitated mimmal directed tree problem. Proc 1980 IEEE Int. Conf on Circuits and Computers, Port Chester, N.Y., Oct. 1980, pp 996-1000
	10	GAVISH, B.Topological design of centralized computer networks--FormulaUons and algorRluns. Networks (to appear)
	11	GAVISH, B., AND HANTLER, S. A Lagranglan relaxation procedure for optimal route selection m SNA networks. Workmg Paper, Graduate School of Management, Univ. of Rochester, Rochester, N.Y., 1982.
	12	GAriSH, B., ^r~I~ SRIKANTIt, K N. O(Nz) algorithms for sensativlty analysis of miatmal spanning trees and related subgraphs D~screte Appl Math. (to appear)
	13	GAVISH, B, AND SRIKANTH, K N. Optmaal solution methods for large-scale multiple-salesmen traveling salesman problem. Manage. Sct (to appear).
	14	GI~OrFR}ON, A.M.Ggrangtan relaxation and its uses m integer programming. Math Program. Study 2 (1974), 82-114
	15	HELD, M., AND KAnt, R.M The traveling salesman problem and minimum sparmmg trees, Part 1. Oper. Res 18 (1970), 1138-1162.
	16	HELD, M., AND KARP, R.M The travehng salesman problem and mimmum spanning trees, Part II. Math. Progrant 1 (1971), 6-25.
	17	HELD, M., WOLFE, P, AND CROWDER, H P Vahdatton of subgradient optimizauon. Math Program. 6 (1974), 62-88.
	18	KARNAU6n, M A new class of algorithms for multapomt network optimization IEEE Trans. Commun C-24, 5 (1976), 500-505.
	19	Kr_e, ZHENBAUM, A.Computing capaotated mmmaal spanning trees efficiently Networks 4, 4 (1974), 299-310.
	20	K~RSHENBAtrM, A., AND BOORSTYN, R R. Centralized teleprocessmg network design. Proc. Nat. Telecommumcauon Conf, New Orleans, La., 1975, pp 2711-2714.
	21	KERSHENBAUM, A., AND BOORS'rYN, R.R Centralized teleprocessing network design. IEEE Trans. Commun. (to appear).
	22	KE~SH~aAtJM, A, BOORSTYN, R R, AND OPPENHE1M, R. Second-order greedy algorithms for centralmed teleprocessmg network design. IEEE Trans Commun. (to appear).
	23	PAPADIMITRIOU, C H.The complexity of the capacitated tree problem. Networks 8 (1978), 217-230.
	24	POLJACK, B T A general method of solwng extremum problems. Soy Math Doklady 8 (1967), 593-597.

CITED BY 8

	Mustafa Yuzukirmizi , J. MacGregor Smith, Optimal buffer allocation in finite closed networks with multiple servers, Computers and Operations Research, v.35 n.8, p.2579-2598, August, 2008
	Alysson M. Costa, A survey on benders decomposition applied to fixed-charge network design problems, Computers and Operations Research, v.32 n.6, p.1429-1450, June 2005
	Luis Gouveia , Pedro Martins, The capacitated minimum spanning tree problem: revisiting hop-indexed formulations, Computers and Operations Research, v.32 n.9, p.2435-2452, September 2005
	R. Patterson , H. Pirkul , E. Rolland, A Memory Adaptive Reasoning Technique for Solving the Capacitated Minimum Spanning Tree Problem, Journal of Heuristics, v.5 n.2, p.159-180, July 1999
	Mauricio C. de Souza , Christophe Duhamel , Celso C. Ribeiro, A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy, Metaheuristics: computer decision-making, Kluwer Academic Publishers, Norwell, MA, 2004
	Raja Jothi , Balaji Raghavachari, Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design, ACM Transactions on Algorithms (TALG), v.1 n.2, p.265-282, October 2005
	Geraldo R. Mateus , Henrique P. L. Luna , Adriana B. Sirihal, Heuristics for Distribution Network Design in Telecommunication, Journal of Heuristics, v.6 n.1, p.131-148, April 2000
	Marc Reimann , Marco Laumanns, Savings based ant colony optimization for the capacitated minimum spanning tree problem, Computers and Operations Research, v.33 n.6, p.1794-1822, June 2006