Minimum-Weight Cycle Covers and Their Approximability

DOI10.1007/978-3-540-74839-7_18zbMath1141.68541OpenAlexW1663062892MaRDI QIDQ3508566

Bodo Manthey

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/minimumweight-cycle-covers-and-their-approximability(b9c53f78-fcd3-445c-8769-0d95f9e6907f).html

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the TSP with sharpened triangle inequality
• Erratum to ``An approximation algorithm for maximum triangle packing
• An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
• On the relationship between ATSP and the cycle cover problem
• Improved deterministic approximation algorithms for max TSP
• An extension of matching theory
• Matching theory
• Classical recursion theory. The theory of functions and sets of natural numbers
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the complexity of the \(k\)-customer vehicle routing problem
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• On Restricted Two-Factors
• Linear approximation of shortest superstrings
• A General Approximation Technique for Constrained Forest Problems
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Algorithms and Data Structures
• Approximation and Online Algorithms