An approximation algorithm for the minimum co-path set problem

DOI10.1007/s00453-010-9389-xzbMath1216.68337OpenAlexW2153743716MaRDI QIDQ547306

Zhi-Zhong Chen, Lusheng Wang, Guo-Hui Lin

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9389-x

zbMATH Keywords

graph algorithmsapproximation algorithmsNP-hardnessco-path setsradiation hybrid mapping

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Kernelization and randomized parameterized algorithms for co-path set problem ⋮ Radiation hybrid map construction problem parameterized

Cites Work

• Unnamed Item
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• An explicit lower bound for TSP with distances one and two
• 8/7-approximation algorithm for (1,2)-TSP
• The Traveling Salesman Problem with Distances One and Two

This page was built for publication: An approximation algorithm for the minimum co-path set problem