On Approximating Restricted Cycle Covers

DOI10.1137/060676003zbMath1165.05028arXivcs/0504038MaRDI QIDQ3614154

Bodo Manthey

Publication date: 16 March 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0504038

zbMATH Keywords

approximation algorithms; inapproximability; cycle covers; two-factors

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Approximability of the minimum-weight \(k\)-size cycle cover problem, Minimum-weight cycle covers and their approximability, Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality, Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem