Paper Info
Title
Multicommodity flows in planar undirected graphs and shortest paths
Abstract
This paper deals with the multicommodity flow problems for two classes of planar undirected graphs. The first class C12 consists of graphs in which each source-sink pair is located on one of two specified face boundaries. The second class C01 consists of graphs in which some of the source-sink pairs are located on a specified face boundary and all the other pairs share a common sink located on the boundary. We show that the multicommodity flow problem for a graph in C12 (resp. C01) can be reduced to the shortest path problem for an undirected (resp. a directed) graph obtained from the dual of the original undirected graph.
Year
DOI
Venue
1985
10.1145/22145.22167
STOC
Keywords
Field
DocType
class c12,multicommodity flow problem,shortest path problem,class c01,specified face boundary,paper deal,source-sink pair,planar undirected graph,original undirected graph,common sink,multicommodity flow,directed graph,shortest path
Block graph,Discrete mathematics,Outerplanar graph,Combinatorics,Comparability graph,Indifference graph,Line graph,Nowhere-zero flow,Pancyclic graph,Mathematics,Graph (abstract data type)
Conference
ISBN
Citations 
PageRank 
0-89791-151-2
4
0.99
References 
Authors
6
3
Name
Order
Citations
PageRank
H. Suzuki123831.31
Takao Nishizeki21771267.08
N. Saito322844.77