The Lattice Structure of Flow in Planar Graphs

DOI10.1137/0406038zbMATH Open0782.90033OpenAlexW2034509988MaRDI QIDQ3136618FDOQ3136618

Authors Samir Khuller, Joseph (Seffi) Naor, Philip N. Klein 

Publication date 14 October 1993

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/ccc2f2055059fca0c6db7bfa824a6a39300b74a4

zbMATH Keywords

distributive latticeminimum cost circulationappropriate sublatticecirculation problem for planar graphsset of integral solutions

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Paths and cycles (05C38)

Recommendations

• Lattices and maximum flow algorithms in planar graphs
• Lattice flows in networks
• scientific article; zbMATH DE number 431512
• Flow in Planar Graphs with Multiple Sources and Sinks
• Lattice structures from planar graphs

Cited in

(20)

• Faster shortest paths in dense distance graphs, with applications
• Decomposition theorem on matchable distributive lattices
• Some flow-equivalent planar and non-planar graphs
• Lattices and maximum flow algorithms in planar graphs
• Willmore flow of planar networks
• A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
• Lattice structures from planar graphs
• Distributive lattices, polyhedra, and generalized flows
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Zero-sum flows of the linear lattice.
• Lattice flows in networks
• Non-matchable distributive lattices
• Maximum flow in directed planar graphs with vertex capacities
• ULD-lattices and \(\Delta \)-bonds
• Title not available (Why is no real title available?)
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
• Title not available (Why is no real title available?)
• Flows in infinite networks represented by vector lattices
• Boundary-to-Boundary Flows in Planar Graphs

This page was built for publication: The Lattice Structure of Flow in Planar Graphs

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