caa a22 4500 445804459 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-010-9389-x doi (NATIONALLICENCE)springer-10.1007/s00453-010-9389-x An Approximation Algorithm for the Minimum Co-Path Set Problem [Elektronische Daten] [Zhi-Zhong Chen, Guohui Lin, Lusheng Wang] 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 of2 and runs in O(n 2) time. Springer Science+Business Media, LLC, 2010 Approximation algorithms nationallicence Graph algorithms nationallicence Co-path sets nationallicence Radiation hybrid mapping nationallicence NP-hardness nationallicence Chen Zhi-Zhong Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan aut Lin Guohui Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada aut Wang Lusheng Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong aut Algorithmica Springer-Verlag 60/4(2011-08-01), 969-986 0178-4617 60:4<969 2011 60 453 https://doi.org/10.1007/s00453-010-9389-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9389-x text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chen Zhi-Zhong Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan aut NATIONALLICENCE 700 1- Lin Guohui Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada aut NATIONALLICENCE 700 1- Wang Lusheng Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 969-986 0178-4617 60:4<969 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer