An O(n log n) algorithm for maximum st-flow in a directed planar graph

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O(n log n) algorithm for maximum st-flow in a directed planar graph

Full text

Pdf (712 KB)

Source

Journal of the ACM (JACM) archive
Volume 56 , Issue 2 (April 2009) table of contents

Article No. 9

Year of Publication: 2009

ISSN:0004-5411

Authors

Glencora Borradaile	Brown University, Providence, Rhode Island
Philip Klein	Brown University, Providence, Rhode Island

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/1502793.1502798 What is a DOI?

ABSTRACT

We give the first correct O(n log n) algorithm for finding a maximum st-flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual s-to-t path.

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	Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	2	Stephen Alstrup , Jacob Holm , Kristian De Lichtenberg , Mikkel Thorup, Maintaining information in fully dynamic trees with top trees, ACM Transactions on Algorithms (TALG), v.1 n.2, p.243-264, October 2005 [doi>10.1145/1103963.1103966]
	3	Therese C. Biedl , Brona Brejová , Tomás Vinar, Simplifying Flow Networks, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, p.192-201, September 01, 2000
	4	Dinitz, E. 1970. Algorithm for solution of a problem of maximum flow in networks with power estimation. Sov. Math. Dokl. 11, 1277--1280.
	5	Edmonds, J. 1960. A combinatorial representation for polyhedral surfaces. Notices AMS 7, 646.
	6	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]
	7	Elias, P., Feinstein, A., and Shannon, C. 1956. A note on the maximum flow through a network. IEEE Trans. Inf. Theory 2, 4, 117--119.
	8	David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook , Moti Yung, Maintenance of a minimum spanning forest in a dynamic planar graph, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.1-11, January 22-24, 1990, San Francisco, California, United States
	9	J. Fakcharoenphol, Planar Graphs, Negative Weight Edges, Shortest Paths, and Near Linear Time, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.232, October 14-17, 2001
	10	Ford, C., and Fulkerson, D. 1956. Maximal flow through a network. Canad. J. Math. 8, 399--404.
	11	Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
	12	Andrew V. Goldberg, Recent Developments in Maximum Flow Algorithms (Invited Lecture), Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, p.1-10, July 08-10, 1998
	13	Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
	14	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
	15	Harris, T., and Ross, F. 1955. Fundamentals of a method for evaluating rail net capacities. Research Memorandum RM-1573, The RAND Corporation, Santa Monica, CA.
	16	Hassin, R. 1981. Maximum flow in (s,t) planar networks. Inf. Proc. Lett. 13, 107.
	17	Hassin, R., and Johnson, D. B. 1985. An O(n log² n) algorithm for maximum flow in undirected planar networks. SIAM J. Comput. 14, 612--624.
	18	Heffter, L. 1891. Über das problem der nachbargebiete. Math. Ann. 38, 477--508.
	19	Monika R. Henzinger , Valerie King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, Journal of the ACM (JACM), v.46 n.4, p.502-516, July 1999 [doi>10.1145/320211.320215]
	20	Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
	21	Itai, A., and Shiloach, Y. 1979. Maximum flow in planar networks. SIAM J. Comput. 8, 135--150.
	22	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
	23	Johnson, D. B., and Venkatesan, S. 1982. Using divide and conquer to find flows in directed planar networks in O(n^3/2 log n) time. In Proceedings of the 20th Annual Allerton Conference on Communication, Control, and Computing. 898--905.
	24	Khuller, S., and Naor, J. 1994. Flow in planar graphs with vertex capacities. Algorithmica 11, 3, 200--225.
	25	Samir Khuller , Joseph Seffi Naor , Philip Klein, The lattice structure of flow in planar graphs, SIAM Journal on Discrete Mathematics, v.6 n.3, p.477-490, Aug. 1993 [doi>10.1137/0406038]
	26	Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	27	Kotzig, A. 1956. Súvislosť a pravidelná súvislosť konečných grafov. Ph.D. dissertation, Vysoká Škola Ekonomická, Bratislava.
	28	Gary L. Miller, Flow in Planar Graphs with Multiple Sources and Sinks, SIAM Journal on Computing, v.24 n.5, p.1002-1017, Oct. 1995 [doi>10.1137/S0097539789162997]
	29	Reif, J. 1983. Minimum s-t cut of a planar undirected network in O(n log² n) time. SIAM Journal on Computing 12, 71--81.
	30	Ripphausen-Lipa, H., Wagner, D., and Weihe, K. 1995. Efficient algorithms for disjoint paths in planar graphs. In Combinatorial Optimization, W. Cook, L. Lovasz, and P. Seymour, Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 20. AMS, 295--354.
	31	Schrijver, A. 2002. On the history of the transportation and maximum flow problems. Math. Prog. 91, 3, 437--445.
	32	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	33	Sommerville, D. 1929. An introduction to the geometry of n dimensions. London.
	34	Robert E. Tarjan , Renato F. Werneck, Self-adjusting top trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	35	Karsten Weihe, Maximum (s,t)-flows in planar networks in O(\|V\| log \|V\|) time, Journal of Computer and System Sciences, v.55 n.3, p.454-475, Dec. 1997 [doi>10.1006/jcss.1997.1538]
	36	Whitney, H. 1933. Planar graphs. Fundamenta mathematicae 21, 73--84.
	37	Youngs, J. 1963. Minimal imbeddings and the genus of a graph. J. Math. Mech. 12, 303--315.

CITED BY 2

	Erin W. Chambers , Jeff Erickson , Amir Nayyeri, Homology flows, cohomology cuts, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Erin W. Chambers , Jeff Erickson , Amir Nayyeri, Minimum cuts and shortest homologous cycles, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark