Algorithms for multicommodity flows in planar graphs |
| |
Authors: | Hitoshi Suzuki Takao Nishizeki Nobuji Saito |
| |
Affiliation: | (1) Department of Electrical Communications, Faculty of Engineering, Tohoku University, 980 Sendai, Japan |
| |
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 inC01 has a face boundaryB1 such that some of the source-sink pairs lie onB1 and all the other pairs share a common sink lying onB1. 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. |
| |
Keywords: | Algorithm Cut condition Muiticommodity flow Network Planar graph Shortest path |
本文献已被 SpringerLink 等数据库收录! |