An approximation algorithm for the minimum co-path set problem

DOI10.1007/S00453-010-9389-XMaRDI QIDQ547306zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Lusheng Wang, Guohui 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

approximation algorithmsgraph algorithmsNP-hardnessco-path setsradiation hybrid mapping

Mathematics Subject Classification ID

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

Recommendations

• An approximation of the minimum vertex cover in a graph
• A 4/3-Approximation Algorithm for Minimum 3-Edge-Connectivity
• An improved approximation algorithm for the minimum 3-path partition problem
• scientific article; zbMATH DE number 2079404
• A fast parameterized algorithm for co-path set

Cites work

• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• 8/7-approximation algorithm for (1,2)-TSP
• 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
• The Traveling Salesman Problem with Distances One and Two

Cited in

(5)

• Radiation hybrid map construction problem parameterized
• An optimal path cover algorithm for cographs
• A fast parameterized algorithm for co-path set
• Kernelization and randomized parameterized algorithms for co-path set problem
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q547306)