Algorithms for multicommodity flows in planar graphs

DOI10.1007/BF01553903zbMath0669.90043OpenAlexW2071650315MaRDI QIDQ1119160

Takao Nishizeki, Nobuji Saito, Hitoshi Suzuki

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553903

zbMATH Keywords

shortest pathcut conditionplanar undirected graphssource-sink pairs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items (2)

Edge-disjoint paths in a grid bounded by two nested rectangles ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• Multicommodity flows in planar graphs
• A data structure for dynamic trees
• Multicommodity flows in graphs
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A quick method for finding shortest pairs of disjoint paths
• On multicommodity flows in planar graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Generalized Nested Dissection
• Two commodity network flows and linear programming

This page was built for publication: Algorithms for multicommodity flows in planar graphs