A matroid approach to finding edge connectivity and packing arborescences

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A matroid approach to finding edge connectivity and packing arborescences

Full text

Pdf (1.31 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 112 - 122

Year of Publication: 1991

ISBN:0-89791-397-3

Author

Harold N. Gabow

Univ. of Colorado at Boulder

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 70, Citation Count: 24

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/103418.103436 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.

	Ed65	J. Edmonds, "Minimum partition of a matroid into independent subsets", J. Res. National Bureau o} Standards 69B, 1965, pp. 67-72.
	Ed69	J. Edmonds, "Submodular functions, matroids, and certain polyhedra", Calgary International Conf. on Combinatorial Structures and their Applications, Gordon and Breach, New York, 1969, pp. 69-87.
	Ed72	J. Edmonds, "Edge-disjoint branchings", in Combinatorial Algorithms, R. Rustin, Ed., Algorithmics Press, New York, 1972, pp. 91-96.
	ET	S. Even and R.E. Tarjan, "Network flow and testing graph connectivity", SIAM J. Comput., 4, 4, 1975, pp. 507-518.
	F	A. Frank, "Kernel systems of directed graphs", Acta Sci. Math., 41, 1979, pp. 63-76.
	G	H.N. Gabow, "Efficient implementations of algorithms to increase edge connectivity", manuscript in preparation.
	GI	Z. Galil and G.F. Italiano, "Reducing edge connectivity to vertex connectivity", manuscript.
	GLS	M. GrStschel, L. Lov~sz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, New York, 1988.
	GT	H.N. Gabow and R.E. Tarjan, "A linear-time algorithm for a special case of disjoint set union", d. Comp. and System Sci., 30, 2, 1985, pp. 209-221.
	GW	Harold Gabow , Herbert Westermann, Forests, frames, and games: algorithms for matroid sums and applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.407-421, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62252]
	GX89a	H.N. Gabow and Y. Xu, "Efficient theoretic and practical algorithms for linear matroid intersection problems", Technical Rept. CU-CS-424-89, Comp. Sci. Dept., Univ. Colorado, Boulder, CO, 1989; submitted for publication.
	GX89b	H.N. Gabow and Y. Xu, "Efficient algorithms for independent assignment on graphic and linear matroids", Proc. 30th Annual Syrup. on Found. o} Comp. Sci., 1989, pp. 106-111.
	KT	A.V. Karzanov and E.A. Timofeev, "Efficient algorithm for finding all minimal edge cuts of a nonoriented graph", Kibernetika, 2, 1986, pp. 8- 12; translated in Cybernetics, 1986, pp. 156-162.
	L75	E.L. Lawler, "Matroid intersection algorithms", Math. Programming, 9, 1975, pp. 31-56.
	L76	E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rhinehart and Winston, New York, 1976.
	Lo	L. LovEsz, "On two minimax theorems in graph theory", J. Comb. Theory, B, #1, 1976, pp. 96- 103.
	M87	D.W. Matula, "Determining edge connectivity in O(nm)", Proc. 28th Annual Syrup. on Found. of Comp. Sci., 1987, pp. 249-251.
	M90	D.W. Matula, "A linear time 2 + e approximation algorithm for edge connectivity", preprint.
	MS	Yishay Mansour , Baruch Schieber, Finding the edge connectivity of directed graphs, Journal of Algorithms, v.10 n.1, p.76-85, Mar. 1989 [doi>10.1016/0196-6774(89)90024-2]
	NI89a	H. Nagamochi and T. Ibaraki, "Linear time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph", Algorithmica, to appear.
	NI89b	H. Nagamochi and T. Ibarald, "Computing edgeconnectivity in multiple and capacitated graphs", Technical Rept. #89009, Dept. of Applied Math. and Physics, Kyoto Univ., 1989.
	P	V.D. Podderyugin, "An algorithm for finding the edge connectivity of graphs," Vopr. Kibern., #2, 1973, p. 136.
	R	A. Recski, Matroid Theory and its Applications in Electric Network Theory and in Statics, Springer- Verlag, New York, 1989.
	RT	J. Roskind and R.E. Tarjan, "A note on finding minimum-cost edge-disjoint spanning trees", Math. Op. Res. 10, 4, 1985, pp. 701-708.
	Sch	C.P. Schnorr, "Bottlenecks and edge connectivity in unsymmetrical networks", SIAM J. Comput., 8, 2, 1979, pp. 265-274.
	Sh	Y. Shiloach, "Edge-disjoint branchings in directed multigraphs", In}. Proc. Letters, 8, 2, 1979, pp. 24-27.
	T74	R.E. Tarjan, "A good algorithm for edge-disjoint branching", Inf. Proc. Letters, 3, 2, 1974, pp. 51- 53.
	T76	R.E. Tarjan, "Edge-disjoint spanning trees and depth-first search", Acta In}ormatica 6, 1976, pp. 171-185.
	T83	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	Th	R. Thurimella, "Finding a sparse k-edge connected spanning subgraph of a k-edge connected graph", preprint.
	Ti	E.A. Timofeev, "An algorithm for constructing minimax k-connected oriented graphs", Kibernetika, P., 1982, p. 109.
	TL	P. Tong and E.L. Lawler, "A faster algorithm for finding edge-disjoint branchings", ln}. Proc. Letters, 17, 2, 1983, pp. 73-76.
	W	D.J.A. Welsh, Matroid Theory, Academic Press, New York, 1976.

CITED BY 24

	Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.759-770, May 04-06, 1992, Victoria, British Columbia, Canada
	Harold N. Gabow, A representation for crossing set families with applications to submodular flow problems, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.202-211, January 25-27, 1993, Austin, Texas, United States
	Zvi Galil , Giuseppe F. Italiano , Neil Sarnak, Fully dynamic planarity testing with applications, Journal of the ACM (JACM), v.46 n.1, p.28-91, Jan. 1999
	Manica Aggarwal , Naveen Garg, A scaling technique for better network design, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.233-240, January 23-25, 1994, Arlington, Virginia, United States
	Harold N. Gabow, Algorithms for graphic polymatroids and parametric s-Sets, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.88-97, January 22-24, 1995, San Francisco, California, United States
	David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States
	András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
	Harold N. Gabow, Efficient splitting off algorithms for graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.696-705, May 23-25, 1994, Montreal, Quebec, Canada
	András A. Benczúr, Augmenting undirected connectivity in RNC and in randomized Õ(n³) time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.658-667, May 23-25, 1994, Montreal, Quebec, Canada
	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997
	David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada
	David R. Karger, Using randomized sparsification to approximate minimum cuts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.424-432, January 23-25, 1994, Arlington, Virginia, United States
	Naveen Garg , Vempala S. Santosh , Aman Singla, Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.103-111, January 25-27, 1993, Austin, Texas, United States
	Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM (JACM), v.41 n.2, p.214-235, March 1994
	Richard Cole , Ramesh Hariharan, A fast algorithm for computing steiner edge connectivity, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Hiroshi Nagamochi , Toshihide Ibaraki, Graph connectivity and its augmentation: applications of MA orderings, Discrete Applied Mathematics, v.123 n.1-3, p.447-472, 15 November 2002
	Esther M. Arkin , Refael Hassin , Shimon Shahar, Increasing digraph arc-connectivity by arc addition, reversal and complement, Discrete Applied Mathematics, v.122 n.1-3, p.13-22, 15 October 2002
	Yunnan Wu , Kamal Jain , Sun-Yuan Kung, A unification of network coding and tree-packing (routing) theorems, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2398-2409, June 2006
	Gruia Calinescu , Peng-jun Wan, Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks, Mobile Networks and Applications, v.11 n.2, p.121-128, April 2006
	Amitabha Bagchi , Ankur Bhargava , Torsten Suel, Approximate maximum weight branchings, Information Processing Letters, v.99 n.2, p.54-58, 31 July 2006
	Zvi Galil , Giuseppe F. Italiano, Reducing edge connectivity to vertex connectivity, ACM SIGACT News, v.22 n.1, p.57-61, Winter 1991
	David Alberts , Monika Rauch Henzinger, Average case analysis of dynamic graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.312-321, January 22-24, 1995, San Francisco, California, United States
	Joachim Reichel , Martin Skutella, Evolutionary algorithms and matroid optimization problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England