An algorithm for multicommodity flows in a class of planar networks
作者:
Hitoshi Suzuki,
Takao Nishizeki,
Nobuji Saito,
期刊:
Electronics and Communications in Japan (Part I: Communications)
(WILEY Available online 1987)
卷期:
Volume 70,
issue 2
页码: 11-18
ISSN:8756-6621
年代: 1987
DOI:10.1002/ecja.4410700202
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractThis paper presents a polynomial‐time algorithm for finding multicommodity flows in planar graphs. Suppose thatGis an undirected planar graph and that some of the source‐sink pairs are located on the boundary of the outer face and all the other pairs share a common sink located on that boundary. The algorithm determines whetherGhas multicommodity flows each from a source to a sink and of a given demand, and if it does, actually finds them.Letnbe the number of vertices inGandbbe the number of edges on the boundary of the outer face. Then the time complexity of the algorithm isO(n(b2+ T+(n)), whereT+(n)is the time required to find the shortest paths from a vertex to the others in a planar‐directed graph withnvertices and nonnegative real weighted edges. In the class of planar networks treated in this paper, it is known that the so‐called “Max Flow ‐ Min Cut the
点击下载:
PDF
(621KB)
返 回