Short length versions of Menger's theorem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Short length versions of Menger's theorem

Full text

Pdf (1.01 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 499 - 508

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Zvi Galil	Department of Computer Science, Columbia University and Tel Aviv Uuiversity
Xiangdong Yu	Department of Computer Science, Columbia University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 23, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/225058.225267 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	R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, "Net-work Flows", Prentice Hall, New Jersey, 199;1.
	2	Ravindra K. Ahuja , Andrew V. Goldberg , James B. Orlin , Robert E. Tarjan, Finding minimum-cost flows by double scaling, Mathematical Programming: Series A and B, v.53 n.3, p.243-266, Feb. 1992 [doi>10.1007/BF01585705]
	3	R. G. Busaker and P.J .Gowen, "A Procedure for De-termining Minimal-Cost Network Flow Patterns", ORO Technical Report 15, 1961, Operational Re-search Office, Johns Hopkins University, 13altirnore, MD.
	4	Robert B. Dial, Algorithm 360: shortest-path forest with topological ordering [H], Communications of the ACM, v.12 n.11, p.632-633, Nov. 1969 [doi>10.1145/363269.363610]
	5	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	6	S.Even and R. E. Tarjan, "Network Flow and Test-ing Graph Connectivity", SIAM .J. on Computing, 4:507-518, 1975.
	7	A. Frank, "Packing Paths, Circuits, and (.hlts-A Survey", Algorithms and C;ornbinatorics 9, Paths, Flows, and VLSI-Layout, Springer-Verlag 1990, pp. 47-1oo.
	8	A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States [doi>10.1145/28395.28397]
	9	F. Harary, "Graph Theory", ,4ddison-Wesley, Reading, Ma, 1969.
	10	M.Iri, "A New Method of Solving Transportation-Network Problems", Journal of the Operations Re-seach Society of Japan 3, 1960, 27-87.
	11	W. S. Jewell, "Optimal Flow through Networks", In-terim Technical Report 8, 1958, Operation Re-search Center, MIT, Cambridge, MA.
	12	R. M. Karp, "Reducibility among Combinatorial Problems", In: Miller, R. E., Thatcher,J.W. (eds.): Complexity of Corrrputer Computations. Plenum Press, New York, NY, pp. 85-103 (IBM Res. Symp. Ser., Vol 4)
	13	S. Khuller and B .Schieber, "Efficient Parallel Algo-rithms for Testing Connectivity, and Finding Dis-joint s - t Paths in Graphs", 30th IEEE Symp. Found. Computer Science19i39, pp 288-293.
	14	L. Lovasz, V. Neumann-Lara and M. D. Plurnmer, "Mengerian theorems for paths with bounded length", Periodica Math. Hung. 9, 1978, pp. 269- 276.
	15	D. W. Matula, '(Determining Edge Connectivity in 0(71771)", 28th IEEE Syrnp. Found. Computer Sci-ence, 1987, pp. '249-251.
	16	K .Menger, "Zur Allgemeinen Kurventheorie", Fun-dam. Math. 10, 1927, pp. 96-115.
	17	James Orlin, A faster strongly polynomial minimum cost flow algorithm, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.377-387, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62249]
	18	N. Robertson and P. D. Seymour, "An Outline of a Disjoint F)aths Algorithm", Combinatorics 9, Paths, Flows, and VLSI-Layout, Springer-Verlag 1990, pp. 267-292.
	19	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	20	N .Tomizava, "On Some Techniques lJseful for So-lution of Transportation Network Problems", Net-works 1, 1972, pp. 173-194.

CITED BY 4

	David R. Karger , Matthew S. Levine, Finding maximum flows in undirected graphs seems easier than bipartite matching, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.69-78, May 24-26, 1998, Dallas, Texas, United States
	Chi-Chang Chen , Jianer Chen, Optimal Parallel Routing in Star Networks, IEEE Transactions on Computers, v.46 n.12, p.1293-1303, December 1997
	Eunseuk Oh , Jianer Chen, On strong Menger-connectivity of star graphs, Discrete Applied Mathematics, v.129 n.2-3, p.499-511, 01 August 2003
	Amitabha Bagchi , Amitabh Chaudhary , Petr Kolman, Short length Menger's theorem and reliable optical routing, Theoretical Computer Science, v.339 n.2, p.315-332, 12 June 2005