Approximately covering by cycles in planar graphs
Dieter Rautenbach, Bruce A. Reed · RWTH Publications (RWTH Aachen) · 2001
Let G = (V(G), E(G)) be a graph and let C be the collection of its cycles. Let p: E(G) r Z+O? be a non-negative, integer-valued function on its edge set.The CYCLE COVER PROBLEM is the optimization problem of finding a multiset a of cycles of G such that each edge e ∈ E is in at least p(e) of the cycles in a and such that the sum of the lengths of all cycles in a is minimum.We will show how to approximate within a factor of 8 the optimum value of the cycle cover problem for planar graphs in polynomial time.