Algorithms for multicommodity flows in planar graphs
type: Item
instance of: scholarly article
title: Algorithms for multicommodity flows in planar graphs
zbMATH Open document ID: 0669.90043
DOI: 10.1007/BF01553903
author: Hitoshi Suzuki
author: Takao Nishizeki
author: Nobuji Saito
published in: Algorithmica
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4097104
zbMATH Keywords: shortest path
zbMATH Keywords: cut condition
zbMATH Keywords: planar undirected graphs
zbMATH Keywords: source-sink pairs
MaRDI profile type: Publication
cites work: Q4091421
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: On multicommodity flows in planar graphs
cites work: Generalized Nested Dissection
cites work: An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
cites work: Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
cites work: Multicommodity flows in graphs
cites work: Multicommodity flows in planar graphs
cites work: Two commodity network flows and linear programming
cites work: A data structure for dynamic trees
cites work: A quick method for finding shortest pairs of disjoint paths
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
cites work: Q3707420
full work available at URL: https://doi.org/10.1007/bf01553903
OpenAlex ID: W2071650315
description: scientific article; zbMATH DE number 4097104