Approximating maximum weight cycle covers in directed graphs with weights zero and one
Bläser, Markus and Manthey, Bodo (2005) Approximating maximum weight cycle covers in directed graphs with weights zero and one. Algorithmica, 42 (2). pp. 121-139. ISSN 0178-4617
Restricted to UT campus only: Request a copy
|Abstract:||A cycle cover of a graph is a spanning subgraph each node of which is part of exactly one simple cycle. A -cycle cover is a cycle cover where each cycle has length at least . Given a complete directed graph with edge weights zero and one, Max--DCC(0, 1) is the problem of finding a k-cycle cover with maximum weight.
We present a approximation algorithm for Max--DCC(0, 1) with running time . This algorithm yields a approximation algorithm for Min--DCC(1, 2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a -cycle cover with minimum weight. We particularly obtain a approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two.
As a lower bound, we prove that Max--DCC(0, 1) for and Max-UCC(0, 1) (finding maximum weight cycle covers in undirected graphs) for are APX-complete.
|Copyright:||© 2005 Springer|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/79421|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page