Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
verfasst von : Bodo Manthey
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
A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An
L
-cycle cover is a cycle cover in which the length of every cycle is in the set
L
⊆ ℕ. For most sets
L
, the problem of computing
L
-cycle covers of maximum weight is NP-hard and APX-hard.
We devise polynomial-time approximation algorithms for
L
-cycle covers. More precisely, we present a factor 2 approximation algorithm for computing
L
-cycle covers of maximum weight in undirected graphs and a factor 20/7 approximation algorithm for the same problem in directed graphs. Both algorithms work for arbitrary sets
L
. To do this, we develop a general decomposition technique for cycle covers.
Finally, we show tight lower bounds for the approximation ratios achievable by algorithms based on such decomposition techniques.