Paper Info
Title
Approximation algorithms for restricted cycle covers based on cycle decompositions
Abstract
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.
Year
DOI
Venue
2006
10.1007/11917496_30
workshop on graph-theoretic concepts in computer science
Keywords
DocType
Volume
general decomposition technique,polynomial-time approximation algorithm,l-cycle cover,approximation ratio,cycle decomposition,decomposition technique,algorithms work,cycle cover,approximation algorithm,restricted cycle,maximum weight,arbitrary set
Conference
abs/cs/0604020
ISSN
ISBN
Citations 
0302-9743
3-540-48381-0
2
PageRank 
References 
Authors
0.37
20
1
Name
Order
Citations
PageRank
Bodo Manthey1635.38