Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
verfasst von : Mingyu Xiao
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.