首页   按字顺浏览 期刊浏览 卷期浏览 An algorithm for multicommodity flows in a class of planar networks
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)



返 回