Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts

Liang Zhao (), Hiroshi Nagamochi () and Toshihide Ibaraki ()
Additional contact information
Liang Zhao: Kyoto University
Hiroshi Nagamochi: Kyoto University
Toshihide Ibaraki: Kyoto University

Journal of Combinatorial Optimization, 2001, vol. 5, issue 4, No 2, 397-410

Abstract: Abstract For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-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 k and 2 − (3k − 4)/(k 2 − k) for an even k. The running time is O(kmn 3 log(n 2/m)) where n and m are the numbers of vertices and edges respectively.

Keywords: undirected graph; approximation algorithm; k-way cut (search for similar items in EconPapers)
Date: 2001
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1011620607786 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:5:y:2001:i:4:d:10.1023_a:1011620607786

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1011620607786

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().