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

cut conditionplanar undirected graphsshortest pathsource-sink pairs

Mathematics Subject Classification ID

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

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

• 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
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Generalized Nested Dissection
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• 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

(15)

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

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)