Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

DOI10.1109/FOCS.2011.73zbMath1292.05237OpenAlexW2058622993WikidataQ60143021 ScholiaQ60143021MaRDI QIDQ5495015

Shay Mozes, Glencora Borradaile, Yahav Nussbaum, Christian Wulff-Nilsen, Philip N. Klein

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.73

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Deterministic network models in operations research (90B10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (13)

NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks ⋮ On computing an optimal semi-matching ⋮ Multiindex transportation problems with 2-embedded structure ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ Orthogonal graph drawing with inflexible edges ⋮ Unnamed Item ⋮ Degree-constrained orientations of embedded graphs ⋮ Accelerated Bend Minimization ⋮ Unnamed Item ⋮ Short and Simple Cycle Separators in Planar Graphs

This page was built for publication: Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time