Lattices and maximum flow algorithms in planar graphs

DOI10.1007/978-3-642-16926-7_30zbMATH Open1310.05201arXiv1211.2189OpenAlexW2102694510MaRDI QIDQ3057636FDOQ3057636

Authors: Jannik Matuschke, Britta Peis 

Publication date: 16 November 2010

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• Lattices and maximum flow algorithms in planar graphs
• Title not available (Why is that?)
• \(k\)-distinct lattice paths
• The Lattice Structure of Flow in Planar Graphs

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)