Algorithms for multicommodity flows in planar graphs

DOI10.1007/BF01553903MaRDI QIDQ1119160zbMATH OpenOpenAlexFDO

Authors Hitoshi Suzuki, Takao Nishizeki, Nobuji Saito

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)

Recommendations

• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• On multicommodity flows in planar graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Flow in Planar Graphs with Multiple Sources and Sinks
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A data structure for dynamic trees
• A linear-time algorithm for a special case of disjoint set union
• A quick method for finding shortest pairs of disjoint paths
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Generalized Nested Dissection
• Multicommodity flows in graphs
• Multicommodity flows in planar graphs
• On multicommodity flows in planar graphs
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Two commodity network flows and linear programming

Cited in

(13)

• Finding edge-disjoint paths in partial k-trees
• Multicommodity flows in certain planar directed networks
• A combinatorial algorithm for the planar multiflow problem with demands located on three holes
• Edge-disjoint paths in a grid bounded by two nested rectangles
• On multicommodity flows in planar graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Multicommodity flows in cycle graphs
• Planar graphs: Theory and algorithms
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Flow in Planar Graphs with Multiple Sources and Sinks
• Designing multi-commodity flow trees

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

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