The Lattice Structure of Flow in Planar Graphs

DOI10.1137/0406038zbMATH Open0782.90033OpenAlexW2034509988MaRDI QIDQ3136618FDOQ3136618

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

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

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

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)

Cited In (20)

• ULD-Lattices and Δ-Bonds
• Faster shortest paths in dense distance graphs, with applications
• Decomposition theorem on matchable distributive lattices
• Some flow-equivalent planar and non-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
• Lattices and Maximum Flow Algorithms in Planar Graphs
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Zero-sum flows of the linear lattice.
• Lattice flows in networks
• Non-matchable distributive lattices
• Maximum flow in directed planar graphs with vertex capacities
• Title not available (Why is that?)
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Title not available (Why is that?)
• 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)