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)

Review text

This paper gives efficient algorithms for two classes \(C_{12}\) and \(C_{01}\) of planar undirected graphs. Every graph in \(C_{12}\) has two face boundaries \(B_ 1\) and \(B_ 2\) such that each of the source-sink pairs lies on \(B_ 1\) or \(B_ 2\). On the other hand, every graph in \(C_{01}\) has a face boundary \(B_ 1\) such that some of the source-sink pairs lie on \(B_ 1\) and all the other pairs share a common sink laying on \(B_ 1\). The algorithms run in \(O(kn+nT(n))\) time if a graph has n vertices and k source-sink pairs and T(n) is the time required for finding the single-source shortest paths in a planar graph of n vertices.

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)