Advertisement
Published in:
2008 | OriginalPaper | Chapter
An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a positive integer
k
and an edge-weighted undirected graph
G
= (
V
,
E
;
w
), the
minimum k
-way cut
problem is to find a subset of edges of minimum total weight whose removal separates the graph into
k
connected components. This problem is a natural generalization of the classical
minimum cut
problem and has been well-studied in the literature.
A simple and natural method to solve the minimum
k
-way cut problem is the divide-and-conquer method: getting a minimum
k
-way cut by properly separating the graph into two small graphs and then finding minimum
k
′-way cut and
k
′′-way cut respectively in the two small graphs, where
k
′ +
k
′′ =
k
. In this paper, we present the first algorithm for the tight case of
$k'=\lfloor k/2\rfloor$
. Our algorithm runs in
$O(n^{4k-\lg k})$
time and can enumerate all minimum
k
-way cuts, which improves all the previously known divide-and-conquer algorithms for this problem.