کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418816 | 681720 | 2009 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Minimum-weight cycle covers and their approximability Minimum-weight cycle covers and their approximability](/preview/png/418816.png)
A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An LL-cycle cover is a cycle cover in which the length of every cycle is in the set L⊆NL⊆N.We investigate how well LL-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 LL. On the other hand, we prove that the problem cannot be approximated with a factor of 2−ε2−ε for certain sets LL.For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n)O(n), where nn is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n)o(n) for certain sets LL.To contrast the results for cycle covers of minimum weight, we show that the problem of computing LL-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1470–1480