Efficient splitting off algorithms for graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient splitting off algorithms for graphs

Full text

Pdf (1.13 MB)

Source

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

Montreal, Quebec, Canada

Pages: 696 - 705

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Harold N. Gabow

Department of Computer Science, University of Colorado at Boulder, Boulder, CO

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 28, Citation Count: 15

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

	B	A.A. Benczfir, "Augmenting undirected connectivity in #)(n3) time", these proceedings.
	E69	J. Edmonds, "Submodular functions, matroids, and certain polyhedra', Calgary International Conf. on Combinatorial Structures and their Ap. plieations, Gordon and Breach, New York, 1969, pp. 69-87.
	F82	A. Frank, "An algorithm for submodulax functions on graphs", in Bonn Workshop on Combinatorial Optimization, A. Bachem, M. Gr6tschel and B. Korte, Eds., Ann. Discrete Math., 16, North- Holland, Amsterdam, 1982, pp. 97-120.
	F84	A. Frank, "Finding feasible vectors of Edmonds- Giles polyhedra', J. Comb. Th.. B. #a, 1984, pp. 221-239.
	F92a	András Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM Journal on Discrete Mathematics, v.5 n.1, p.25-53, Feb. 1992 [doi>10.1137/0405003]
	F92b	András Frank, On a theorem of Mader, Discrete Mathematics, v.101 n.1-3, p.49-57, May 29, 1992 [doi>10.1016/0012-365X(92)90589-8]
	F93	András Frank, Applications of submodular functions, Surveys in combinatorics, 1993, Cambridge University Press, New York, NY, 1993
	FF	L.R. Ford, Jr. and D.R. Fulkerson, Flows in Networks, Princeton Univ. Press, Princeton, NJ, 1962.
	Ga91a	Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.112-122, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103436]
	Ga91b	Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
	Ga93a	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
	Ga93b	H.N. Gabow, "A framework for cost-scaling algorithms for submodular flow problems", Proc. 34th Annual Syrup. on Found. of Comp. Sci., 1993, pp. 449-458; also Tech. Rept. CU-CS-661-93, Dept. of Comp. Sci., Univ. of Col. at Boulder, Boulder, CO, 1993.
	HO	Jianxiu Hao , James B. Orlin, A faster algorithm for finding the minimum cut in a graph, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.165-174, September 1992, Orlando, Florida, United States
	L	L. Lov#sz, Combinatorial Problems and Exercises, 2nd Ed., North-Holland, New York, 1993.
	M	W. Maxler, "A reduction method for edgeconnectivity in graphs", Ann. Discrete Math., 3, 1978, pp. 145-164.
	NGM	D. Naor, D. Gusfield and C. Martd, "A fast algorithm for optimally increasing the edgeconnectivity", Proc. 31st Annual Syrup. on Found. o.f Comp. Sci., 1990, pp. 698-707.
	NI	H. Nagamochi and T. Ibaxaki, "A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph", Algorithmica, 7, 1992, pp. 583-596.
	NW	C. St. J. A. Nash-Williams, "On orientations, connectivity and odd vertex pairings in finite graphs", Canadian J. Math., lYt, 1960, pp. 555-567.
	R	H.E. Robbins, "A theorem on graphs with an application to a problem of traffic control", American Math. Monthly, #6, 1939, pp. 281-283.
	TTT	Éva Tardos , Craig A Tovey , Michael A Trick, Layered augmenting path algorithms, Mathematics of Operations Research, v.11 n.2, p.362-370, May 1986 [doi>10.1287/moor.11.2.362]

CITED BY 15

	Hiroshi Nagamochi , Takashi Shiraki , Toshihide Ibaraki, Computing edge-connectivity augmentation function in Õ(nm) time, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.649-658, January 05-07, 1997, New Orleans, Louisiana, United States
	Toshimasa Ishii , Hiroshi Nagamochi , Toshihide Ibaraki, Optimal augmentation to make a graph k-edge-connected and triconnected, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.280-289, January 25-27, 1998, San Francisco, California, United States
	András A. Benczúr , David R. Karger, Augmenting undirected edge connectivity in Õ(n2) time, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.500-509, January 25-27, 1998, San Francisco, California, 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
	Hiroshi Nagamochi , Toshihide Ibaraki, Deterministic Õ(nm) time edge-splitting in undirected graphs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.64-73, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	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
	András A. Benczúr, Pushdown-reduce: an algorithm for connectivity augmentation and poset covering problems, Discrete Applied Mathematics, v.129 n.2-3, p.233-262, 01 August 2003
	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
	László A. Végh , András A. Benczúr, Primal-dual approach for directed vertex connectivity augmentation and generalizations, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Zoltán Király , Zoltán Szigeti, Simultaneous well-balanced orientations of graphs, Journal of Combinatorial Theory Series B, v.96 n.5, p.684-692, September 2006
	Toshimasa Ishii, Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs, Proceedings of the thirteenth Australasian symposium on Theory of computing, p.91-100, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Attila Bernáth , Gwenaël Joret, Well-balanced orientations of mixed graphs, Information Processing Letters, v.106 n.4, p.149-151, May, 2008
	László A. VéghVégh , András A. Benczúr, Primal-dual approach for directed vertex connectivity augmentation and generalizations, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-21, May 2008
	Anand Bhalgat , Ramesh Hariharan , Telikepalli Kavitha , Debmalya Panigrahi, Fast edge splitting and Edmonds' arborescence construction for unweighted graphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.455-464, January 20-22, 2008, San Francisco, California
	Anand Bhalgat , Ramesh Hariharan, Fast edge orientation for unweighted graphs, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.265-272, January 04-06, 2009, New York, New York