An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
From MaRDI portal
Publication:3452205
DOI10.1145/1502793.1502798zbMath1325.05161OpenAlexW2008597108MaRDI QIDQ3452205
Glencora Borradaile, Philip N. Klein
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1502793.1502798
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)
Related Items
Minimum Cuts in Surface Graphs, Depth-first search in directed planar graphs, revisited, A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks, TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, How vulnerable is an undirected planar graph with respect to max flow, 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, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Counting and sampling minimum cuts in genus \(g\) graphs, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, Min-Cost Flow in Unit-Capacity Planar Graphs, Accelerated Bend Minimization, Single-source shortest paths and strong connectivity in dynamic planar graphs, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Faster algorithms for shortest path and network flow based on graph decomposition, Planar Digraphs, Unnamed Item
