Lattices and maximum flow algorithms in planar graphs

DOI10.1007/978-3-642-16926-7_30MaRDI QIDQ3057636zbMATH OpenOpenAlexFDO

Authors Jannik Matuschke, Britta Peis

Publication date 16 November 2010

Published in Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.2189

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21) Semimodular lattices, geometric lattices (06C10)

Abstract: We show that the left/right relation on the set of s-t-paths of a plane graph induces a so-called submodular lattice. If the embedding of the graph is s-t-planar, this lattice is even consecutive. This implies that Ford and Fulkerson's uppermost path algorithm for maximum flow in such graphs is indeed a special case of a two-phase greedy algorithm on lattice polyhedra. We also show that the properties submodularity and consecutivity cannot be achieved simultaneously by any partial order on the paths if the graph is planar but not s-t-planar, thus providing a characterization of this class of graphs.

Recommendations

• The Lattice Structure of Flow in Planar Graphs
• An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Minimum flows in directed \(s\)-\(t\) planar networks
• Maximum flow in directed planar graphs with vertex capacities

Cites work

• scientific article; zbMATH DE number 5764848 (Why is no real title available?)
• scientific article; zbMATH DE number 3634046 (Why is no real title available?)
• scientific article; zbMATH DE number 3634269 (Why is no real title available?)
• An O (n log n) algorithm for maximum st-flow in a directed planar graph
• Increasing the rooted connectivity of a digraph by one
• Lattices and maximum flow algorithms in planar graphs
• Maximal Flow Through a Network
• Maximum Flow in Planar Networks
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Multiple-source shortest paths in planar graphs
• The Lattice Structure of Flow in Planar Graphs
• ULD-lattices and \(\Delta \)-bonds

Cited in

(4)

• Lattices and maximum flow algorithms in planar graphs
• scientific article; zbMATH DE number 6297748 (Why is no real title available?)
• The Lattice Structure of Flow in Planar Graphs
• \(k\)-distinct lattice paths

This page was built for publication: Lattices and maximum flow algorithms in planar graphs

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