2000年
Approximating the minimum k-way cut in a graph via minimum 3-way cuts
ALGORITHMS AND COMPUTATIONS
- ,
- ,
- 巻
- 1741
- 号
- 開始ページ
- 373
- 終了ページ
- 382
- 記述言語
- 英語
- 掲載種別
- 記事・総説・解説・論説等(国際会議プロシーディングズ)
- DOI
- 10.1007/3-540-46632-0_38
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
For an edge weighted undirected graph G and an integer k greater than or equal to 2, a k-way cut is a set of edges whose removal leaves G with at least Ic components. We propose a simple approximation algorithm to the minimum Ic-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 - 3/k for an odd Ic: and 2 - (3k - 4)/(k(2) - k) for an even Ic. The running time is O(kmn(3) log(n(2)/m)) where n, and m are the numbers of vertices and edges respectively.
- リンク情報
-
- DOI
- https://doi.org/10.1007/3-540-46632-0_38
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000165143000038&DestApp=WOS_CPL
- URL
- https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84949424651&origin=inward
- ID情報
-
- DOI : 10.1007/3-540-46632-0_38
- ISSN : 0302-9743
- SCOPUS ID : 84949424651
- Web of Science ID : WOS:000165143000038