An approximation algorithm for the minimum co-path set problem

DOI10.1007/S00453-010-9389-XzbMATH Open1216.68337OpenAlexW2153743716MaRDI QIDQ547306FDOQ547306

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

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

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)

Cites Work

• 8/7-approximation algorithm for (1,2)-TSP
• The Traveling Salesman Problem with Distances One and Two
• An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
• Title not available (Why is that?)
• An explicit lower bound for TSP 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)