Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Divide-and-Color
verfasst von : Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith
Erschienen in: Graph-Theoretic Concepts in Computer Science
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
We introduce
divide-and-color
, a new technique for the solution of hard graph problems. It is a combination of the well-known
divide-and-conquer
paradigm and
color-coding
[2]. Our approach first randomly colors all edges or nodes of a graph black and white, and then solves the problem recursively on the two induced parts.
We demonstrate this technique by giving new randomized algorithms for the solution of two important problems. These yield runtime bounds of
O
*
(4
k
) for finding a simple path of length
k
and
O
*
(4
( h − − 1) k
) for finding
k
edge-disjoint (resp. vertex-disjoint) copies of a graph
H
with
h
edges (resp.
h
nodes) in a given graph. Derandomization gives deterministic algorithms for these problems with running times
O
*
(2
4 k
) and
O
*
(2
4hk
), respectively.
All these results significantly improve over the currently known best bounds. In particular, our generic algorithms beat specialized ones that have been designed to find
k
triangles or paths of length two.