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

DOI10.1145/1109557.1109615MaRDI QIDQ3581580zbMATH OpenOpenAlexFDO

Authors Glencora Borradaile, Philip N. Klein

Publication date 16 August 2010

Published in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1109557.1109615

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Cited in

(6)

• Greedy oriented flows
• A ranking model for the greedy algorithm and discrete convexity
• Lattices and maximum flow algorithms in planar graphs
• Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
• Counting and sampling minimum cuts in genus g graphs
• Minimum Cuts in Surface Graphs

This page was built for publication: An O (n log n) algorithm for maximum st-flow in a directed planar graph

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