The Lattice Structure of Flow in Planar Graphs

DOI10.1137/0406038zbMath0782.90033OpenAlexW2034509988MaRDI QIDQ3136618

Joseph (Seffi) Naor, Samir Khuller, 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)

Related Items (12)

A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs ⋮ Decomposition theorem on matchable distributive lattices ⋮ Distributive lattices, polyhedra, and generalized flows ⋮ 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 ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Maximum flow in directed planar graphs with vertex capacities ⋮ Non-matchable distributive lattices ⋮ ULD-Lattices and Δ-Bonds ⋮ Lattice flows in networks ⋮ Lattices and Maximum Flow Algorithms in Planar Graphs ⋮ Transversal structures on triangulations: A combinatorial study and straight-line drawings

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