A New Bound for the Path Cover Problem
We consider the path cover problem which is to find a set of vertex-disjoint paths for a simple undirectedgraph with maximum number of edges to cover all vertices of this graph.The path cover problem isNP-hard because the well known Hamilton path problem is NP complete and the Hamilton path problemis a special case of the path cover problem.In this paper we present a new upper bound for the size of asolution of the path cover problem We believe that the upper bound is useful for our future research.Asan application,we devise a 7-10approximation algorithm whose time complexity is O(|V‖E|1.5log(|V|))where |V| is the number of vertices and |E| is the number of edges of a graph.Recall that the bestapproximation ratio is 6-7 which is achieved by Berman et al”20”.However,their algorithm has timecomplexity O(|V|9) which is much slower than ours.
approximation algorithm upper bound path cover
Xingfu Li Daming Zhu
School of Computer Science and Technology,Shandong University,Jinan,Shandong 250100,China
国内会议
济南
英文
1-17
2014-10-16(万方平台首次上网日期,不代表论文的发表时间)