Maximum Flow in Directed Planar Graphs with Vertex Capacities

DOI10.1007/978-3-642-04128-0_36MaRDI QIDQ3639262zbMATH OpenOpenAlexFDO

Authors Haim Kaplan, Yahav Nussbaum

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_36

zbMATH Keywords

capacity constraintsdirected planar graphmaximum flow

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Maximum flow in directed planar graphs with vertex capacities
• Flow in planar graphs with vertex capacities
• Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
• Maximum integer flows in directed planar graphs with vertex capacities and multiple sources and sinks
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time

Cited in

(12)

• Flow in planar graphs with vertex capacities
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Maximum s-t-flow with k crossings in O(k^3 n n) time
• scientific article; zbMATH DE number 431512 (Why is no real title available?)
• Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities
• Max flow vitality in general and st-planar graphs
• Maximum integer flows in directed planar graphs with vertex capacities and multiple sources and sinks
• scientific article; zbMATH DE number 6297748 (Why is no real title available?)
• Max Flows in Planar Graphs with Vertex Capacities
• How vulnerable is an undirected planar graph with respect to max flow
• Maximum flow in directed planar graphs with vertex capacities
• Flow equivalent trees in undirected node-edge-capacitated planar graphs

This page was built for publication: Maximum Flow in Directed Planar Graphs with Vertex Capacities

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