Algorithms for plane multicommodity flows

DOI Web Site Web Site 参考文献8件

書誌事項

公開日
1984-01
権利情報
  • http://onlinelibrary.wiley.com/termsAndConditions#vor
DOI
  • 10.1002/ecja.4400670203
公開者
Wiley

この論文をさがす

説明

<jats:title>Abstract</jats:title><jats:p>This paper presents a polynomial‐time algorithm which can determine the multicommodity flows in a planar undirected graph G. It is assumed that G remains planar if an edge is added between each source‐sink pair. Given positive and real demand to each source‐sink pair, the algorithm determines whether or not there exists a multicommodity flow in G realizing the specified demand, i.e., feasibility, and if it exists, the multicommodity flow is determined. It is shown that by solving the maximum‐weight matching problem once for a graph which is a modification of the graph dual to the given graph G, the feasibility is determined, and by solving the problem for 0(kn) times, the multicommodity flows are determined. Consequently, if G has n vertices and k source‐sink pairs, the computation time required to determine the feasibility is 0(n2 log n), and the time required to determine the k‐commodity flow is 0(kn3 log n). the memory storage required is 0(kn). It is known that the maximum‐flow min‐cut theorem exists for the case of planar graph considered in this paper.</jats:p>

収録刊行物

参考文献 (8)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ