An approximation algorithm for the minimum co-path set problem

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

7 Scopus Citations
Scopus Metrics
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)969-986
Journal / PublicationAlgorithmica (New York)
Volume60
Issue number4
Publication statusPublished - Aug 2011

Link(s)

DOI

DOI
Check@CityULib
Link to Scopus https://www.scopus.com/record/display.uri?eid=2-s2.0-79959216521&origin=recordpage
Permanent Link https://scholars.cityu.edu.hk/en/publications/publication(30ea9c26-068c-4304-a0d4-61e6ded58526).html

Abstract

We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of 10/7 and runs in O(n 1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio of 2 and runs in O(n 2) time. © 2010 Springer Science+Business Media, LLC.

Research Area(s)

  • Approximation algorithms, Co-path sets, Graph algorithms, NP-hardness, Radiation hybrid mapping

Fingerprint

Publication fingerprints text

100
Algorithm Engineering
100
Approximation Algor... Computer Science
100
Path Set Keyphrases
100
algorithms INIS
100
approximations INIS
100
graphs INIS
100
Approximation Mathematics
33
Leaf Engineering
33
Connected Component Engineering
33
Best Approximation Keyphrases
Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]
An approximation algorithm for the minimum co-path set problem. / Chen, Zhi-Zhong; Lin, Guohui; Wang, Lusheng.
In: Algorithmica (New York), Vol. 60, No. 4, 08.2011, p. 969-986.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review