Name
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@?N. We investigate how well L-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 L. On the other hand, we prove that the problem cannot be approximated with a factor of 2-@e for certain sets L. For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n) for certain sets L. To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.dam.2008.10.005 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
approximation ratio,approximation algorithms,asymptotically optimal,minimum weight,minimum-weight cycle cover,certain set,maximum weight,constant approximation ratio,l-cycle cover,non-constructive algorithms,set l,inapproximability,cycle cover,cycle covers,non-constructive polynomial-time approximation algorithm,directed graph | Conference | 157 |
Issue | ISSN | ISBN |
7 | Discrete Applied Mathematics | 3-540-74838-5 |
Citations | PageRank | References |
2 | 0.43 | 24 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bodo Manthey | 1 | 63 | 5.38 |