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.
| Original language | English |
|---|---|
| Pages (from-to) | 969-986 |
| Journal | Algorithmica (New York) |
| Volume | 60 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - Aug 2011 |
Research Keywords
- Approximation algorithms
- Co-path sets
- Graph algorithms
- NP-hardness
- Radiation hybrid mapping
Fingerprint
Dive into the research topics of 'An approximation algorithm for the minimum co-path set problem'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver