Solving the path cover problem on circular-arc graphs by using an approximation algorithm

作     者：Hung, RW Chang, MS 

作者机构：Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 621 Taiwan 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2006年第154卷第1期

页      面：76-105页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：National Science Council of Republic of China  (NSC82-0408-E-194-028) 

主　　题：graph algorithms path cover Hamiltonian cycle Hamiltonian path interval graphs circular-arc graphs 

摘      要：A path cover of a graph G = (V, E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs. (c) 2005 Elsevier B.V. All rights reserved.