Article

Maximum s-t-flow with k crossings in O(k³n log n) time

Authors:

Jan M. Hochstein,

Karsten WeiheAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 843 - 847

Published: 07 January 2007 Publication History

Get Access

Abstract

There is a large body of results on planar graph algorithms that are more efficient than the best known algorithm for general graphs [13]. Maximum flow [1] is but one example. More drastically, the maximum cut problem is polynomially solvable for planar instances but NP-complete in general [12, 8, 5].

However, little is known about nearly planar graphs. This is unsatisfactory since the nearly planar case is particularly important in practice. Think for example of road networks with bridges and tunnels.

We present a preflow push algorithm that solves the maximum s-t-flow problem in a network with n vertices and m edges and embedded with k crossings in time O(k³n log n) worst case. To our knowledge there is only one previous result that relates asymptotic running time to a topological parameter of the graph such that the running time is polynomial in this parameter.

Compared with the currently fastest maximum flow algorithms this reduces the worst case running time by a factor of m/k³ ignoring logarithmic factors. Therefore, it is particularly favorable for very sparse or nearly planar graphs.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Prentice-Hall, Englewood Cliffs, New Jersey, 1993.

Google Scholar

[2]

Glencora Borradaile and Philip Klein. An O(n log n) algorithm for maximum st-flow in a directed planar graph. In SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithms, pages 524--533, 2006.

Digital Library

Google Scholar

[3]

J. Cheriyan and S. N. Maheshwari. Analysis of preflow push algorithms for maximum network flow. SIAM J. Comput., 18(6):1057--1086, 1989.

Digital Library

Google Scholar

[4]

Fedor V. Fomin and Dimitrios M. Thilikos. Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In ICALP 2004: Automata, Languages and Programming: 31st International Colloquium, volume 3142 of Lecture Notes in Computer Science, pages 581--592, 2004.

Google Scholar

[5]

M. Garey and D. Johnson. Computers and Intractability. W. H. Freeman & Co., San Francisco, 1979.

Google Scholar

[6]

Andrew V. Goldberg and Robert Endre Tarjan. A new approach to the maximum-flow problem. J. ACM, 35(4):921--940, 1988.

Digital Library

Google Scholar

[7]

J. L. Gross and T. W. Tucker. Topological Graph Theory. John Wiley and Sons, New York, 1987.

Digital Library

Google Scholar

[8]

F. O. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4:221--225, 1975.

Google Scholar

[9]

J. Reif I. S. Filotti, G. L. Miller. On determining the genus of a graph in O(v^O(g) ) steps. In STOC '79: Proceedings of the 11th annual ACM Symposium on the Theory of Computing, pages 27--37, 1979.

Digital Library

Google Scholar

[10]

Martin Mareš. Two linear time algorithms for MST on minor closed graph classes. Archivum Mathematicum, 40(3):315--320, 2004.

Google Scholar

[11]

Gary Miller. Isomorphism testing for graphs of bounded genus. In STOC '80: Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 225--235, 1980.

Digital Library

Google Scholar

[12]

G. I. Orlova and Y. G. Dorfman. Finding the maximum cut in a graph. Engineering Cybernetics, 10:502--506, 1972.

Google Scholar

[13]

H. Ripphausen-Lipa, D. Wagner, and K. Weihe. Efficient algorithms for disjoint paths in planar graphs, volume 20, pages 295--354. American Mathematical Society, Providence, RI, 1995.

Google Scholar

[14]

Karsten Weihe. Maximum (s, t)-flows in planar networks in O(|V|log|V|) time. Journal of Computer and System Sciences, 55(3):454--475, December 1997.

Digital Library

Google Scholar

Cited By

View all

Chimani MHedtke IWiedera T(2019)Exact Algorithms for the Maximum Planar Subgraph ProblemACM Journal of Experimental Algorithmics10.1145/332034424(1-21)Online publication date: 25-Apr-2019
https://dl.acm.org/doi/10.1145/3320344
Chambers EErickson JNayyeri AHershberger JFogel E(2009)Minimum cuts and shortest homologous cyclesProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542426(377-385)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542426
Chambers EErickson JNayyeri AMitzenmacher M(2009)Homology flows, cohomology cutsProceedings of the forty-first annual ACM symposium on Theory of computing10.1145/1536414.1536453(273-282)Online publication date: 31-May-2009
https://dl.acm.org/doi/10.1145/1536414.1536453

Maximum s-t-flow with k crossings in O(k³n log n) time
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

An o(n^3)-Time Algorithm Maximun-Flow Algorithm

We show that a maximum flow in a network with $n$ vertices can be computed deterministically in $O(n^3/\log n)$ time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of $O(n^3)$.

The bottleneck in our algorithm is a ...
Tutte’s 3-flow Conjecture for almost even graphs
Abstract
A 3-flow for a graph G is an assignment of directions and weights in {1, 2} to the edges of G, such that the netsum of weights on the edges incident to every vertex of G is equal to zero (weights on incoming and outgoing edges are added with ...
The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture

Let k be an odd natural number ź5, and let G be a ( 6 k - 7 ) -edge-connected graph of bipartite index at least k - 1 . Then, for each mapping f : V ( G ) ź N , G has a subgraph H such that each vertex v has H-degree f ( v ) modulo k. We apply this to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
336
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chimani MHedtke IWiedera T(2019)Exact Algorithms for the Maximum Planar Subgraph ProblemACM Journal of Experimental Algorithmics10.1145/332034424(1-21)Online publication date: 25-Apr-2019
https://dl.acm.org/doi/10.1145/3320344
Chambers EErickson JNayyeri AHershberger JFogel E(2009)Minimum cuts and shortest homologous cyclesProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542426(377-385)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542426
Chambers EErickson JNayyeri AMitzenmacher M(2009)Homology flows, cohomology cutsProceedings of the forty-first annual ACM symposium on Theory of computing10.1145/1536414.1536453(273-282)Online publication date: 31-May-2009
https://dl.acm.org/doi/10.1145/1536414.1536453

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

An o(n^3)-Time Algorithm Maximun-Flow Algorithm

Tutte’s 3-flow Conjecture for almost even graphs

The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture