Approximating maximum weight cycle covers in directed graphs with weights zero and one

DOI10.1007/s00453-004-1131-0zbMath1079.68068OpenAlexW2051080684MaRDI QIDQ2483998

Bodo Manthey, Markus Bläser

Publication date: 2 August 2005

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://doc.rero.ch/record/315085/files/453_2004_Article_1131.pdf

zbMATH Keywords

Traveling salesman problemCombinatorial optimizationApproximation algorithmsInapproximabilityCycle covers

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (11)

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems ⋮ The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings ⋮ Approximability of the minimum-weight \(k\)-size cycle cover problem ⋮ An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles ⋮ Minimum-Weight Cycle Covers and Their Approximability ⋮ New Approximation Algorithms for (1,2)-TSP ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ Deterministic algorithms for multi-criteria max-TSP ⋮ Minimum-weight cycle covers and their approximability ⋮ (1,2)-HAMILTONIAN COMPLETION ON A MATCHING

This page was built for publication: Approximating maximum weight cycle covers in directed graphs with weights zero and one