History

Please fill in your query. A complete syntax description you will find on the General Help page.
An approximation algorithm for the minimum co-path set problem. (English)
Algorithmica 60, No. 4, 969-986 (2011).
Summary: 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 $\frac {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.