Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
| dc.creator | Manthey, Bodo | |
| dc.date | 2006-04-06 | |
| dc.date | 2006-12-15 | |
| dc.date.accessioned | 2026-07-07T07:35:15Z | |
| dc.date.available | 2026-07-07T07:35:15Z | |
| dc.description | 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. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is APX-hard and NP-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated within a factor of 2 for undirected graphs and within a factor of 8/3 in the case of directed graphs. This holds for arbitrary sets L. | |
| dc.description | This paper has been joint with "On Approximating Restricted Cycle Covers" (cs.CC/0504038). Please refer to that paper. The paper "Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions" is now obsolete | |
| dc.identifier | https://arxiv.org/abs/cs/0604020 | |
| dc.identifier | http://arxiv.org/abs/cs/0604020 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/120034 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2; G.2.1; G.2.2 | |
| dc.title | Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions | |
| dc.type | text |