Maximum Flow in Planar Networks

DOI10.1137/0208012zbMath0419.90040OpenAlexW2039086323MaRDI QIDQ3853414

Alon Itai, Yossi Shiloach

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b83835db99723f922b7b286d10952b08c68970a7

zbMATH Keywords

computational complexityplanar graphmaximum flowplanar networksdirected flow network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items

Minimum Cuts in Surface Graphs, Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time, How vulnerable is an undirected planar graph with respect to max flow, An \(O(EV\log^2V)\) algorithm for the maximal flow problem, Faster shortest paths in dense distance graphs, with applications, How vulnerable is an undirected planar graph with respect to max flow, Maximum flow in directed planar graphs with vertex capacities, On maximum flows in polyhedral domains, Counting and sampling minimum cuts in genus \(g\) graphs, Allocation under a general substitution structure, Bounding the variance in Monte Carlo experiments, Lattices and Maximum Flow Algorithms in Planar Graphs, Level-planar drawings with few slopes, Level-planar drawings with few slopes, Unnamed Item, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Evaluating Reliability of Stochastic Flow Networks, Capacity Expansion in Stochastic Flow Networks, A linear-time algorithm for edge-disjoint paths in planar graphs, Unnamed Item, Flow in planar graphs with vertex capacities, A note on finding minimum cuts in directed planar networks by parallel computations