MISC

査読有り
2000年

Approximating the minimum k-way cut in a graph via minimum 3-way cuts

ALGORITHMS AND COMPUTATIONS
  • L Zhao
  • ,
  • H Nagamochi
  • ,
  • T Ibaraki

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

エクスポート
BibTeX RIS