The Lattice Structure of Flow in Planar Graphs

DOI10.1137/0406038MaRDI QIDQ3136618zbMATH OpenOpenAlexFDO

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

appropriate sublatticecirculation problem for planar graphsdistributive latticeminimum cost circulationset of integral solutions

Mathematics Subject Classification ID

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

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

(25)

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

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)