An Approximation Algorithm for the Minimum Co-Path Set Problem |
| |
| Authors: | Zhi-Zhong Chen Guohui Lin Lusheng Wang |
| |
| Affiliation: | 1.Department of Mathematical Sciences,Tokyo Denki University,Saitama,Japan;2.Department of Computing Science,University of Alberta,Edmonton,Canada;3.Department of Computer Science,City University of Hong Kong,Kowloon,Hong Kong |
| |
| 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
\frac 107\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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
