会议专题

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

国内会议

2014全国理论计算机科学学术年会

济南

英文

1-17

2014-10-16(万方平台首次上网日期,不代表论文的发表时间)