A New Algorithm for p-Collection Problem on a Tree-Type Flow Network

スポンサーリンク

概要

• 論文の詳細を見る

• For given integer p, a flow network N with n vertices, and sources in N, a problem of finding location of p sinks in N which maximize the value of maximum flow from sources to sinks is called p-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network,which is simpler and more efficient than the previous algorithm, and has time complexity of O(p^2n^2C_c・min{C_c,C_d}), where C_c and C_d are the maximum edge capacity and the maximum vertex weight, respectively.

• 社団法人電子情報通信学会の論文
• 1998-01-25

著者

• Tsukiyama Shuji

  Department Electrical And Electronic Eng. Chuo University

関連論文

• Transistor Sizing of LCD Driver Circuit for Technology Migration(Circuit Synthesis,VLSI Design and CAD Algorithms)
• An Algorithm for Generating All The Directed Paths and Its Application
• A New Algorithm for p-Collection Problem on a Tree-Type Flow Network
• An Algorithm to Position Fictitious Terminals on Borders of Divided Routing Areas (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク