TY - JOUR
T1 - An approximation algorithm for the minimum co-path set problem
AU - Chen, Zhi-Zhong
AU - Lin, Guohui
AU - Wang, Lusheng
PY - 2011/8
Y1 - 2011/8
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Co-path sets
KW - Graph algorithms
KW - NP-hardness
KW - Radiation hybrid mapping
UR - http://www.scopus.com/inward/record.url?scp=79959216521&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79959216521&origin=recordpage
U2 - 10.1007/s00453-010-9389-x
DO - 10.1007/s00453-010-9389-x
M3 - RGC 21 - Publication in refereed journal
VL - 60
SP - 969
EP - 986
JO - Algorithmica (New York)
JF - Algorithmica (New York)
SN - 0178-4617
IS - 4
ER -