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

DOI10.1109/FOCS.2011.73MaRDI QIDQ5495015zbMATH OpenOpenAlexWikidataFDO

Authors Glencora Borradaile, Shay Mozes, 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) Deterministic network models in operations research (90B10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited in

(13)

• scientific article; zbMATH DE number 7559248 (Why is no real title available?)
• Accelerated bend minimization
• A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Near-optimal distance emulator for planar graphs
• Orthogonal graph drawing with inflexible edges
• A simple reduction from maximum weight matching to maximum cardinality matching
• NC algorithms for weighted planar perfect matching and related problems
• On computing an optimal semi-matching
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• Short and simple cycle separators in planar graphs
• Multiindex transportation problems with 2-embedded structure
• Degree-constrained orientations of embedded graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495015)