Minimum-weight cycle covers and their approximability
Manthey, B. (2009) Minimum-weight cycle covers and their approximability. Discrete Applied Mathematics, 157 (7). pp. 1470-1480. ISSN 0166-218X
Restricted to UT campus only: Request a copy
|Abstract:||A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An -cycle cover is a cycle cover in which the length of every cycle is in the set .|
We investigate how well -cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets . On the other hand, we prove that the problem cannot be approximated with a factor of for certain sets .
For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of , where is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of for certain sets .
To contrast the results for cycle covers of minimum weight, we show that the problem of computing -cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/68062|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page