ISSN:
1432-0541
Keywords:
Algorithm
;
Cut condition
;
Muiticommodity flow
;
Network
;
Planar graph
;
Shortest path
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract This paper gives efficient algorithms for the muiticommodity flow problem for two classes C12 and C01 of planar undirected graphs. Every graph in C12 has two face boundaries B1 and B2 such that each of the source-sink pairs lies on B1 or B2. On the other hand, every graph inC 01 has a face boundaryB 1 such that some of the source-sink pairs lie onB 1 and all the other pairs share a common sink lying onB 1. The algorithms run inO(kn +nT(n)) time if a graph hasn vertices andk source-sink pairs andT(n) is the time required for finding the single-source shortest paths in a planar graph ofn vertices.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01553903
Permalink
