Premium
A linear‐time algorithm for the k ‐fixed‐endpoint path cover problem on cographs
Author(s) -
Asdre Katerina,
Nikolopoulos Stavros D.
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20200
Subject(s) - cover (algebra) , combinatorics , mathematics , path (computing) , disjoint sets , vertex (graph theory) , vertex cover , fixed point , discrete mathematics , set cover problem , cardinality (data modeling) , time complexity , graph , set (abstract data type) , computer science , mechanical engineering , mathematical analysis , engineering , data mining , programming language
Abstract In this paper, we study a variant of the path cover problem, namely, the k ‐fixed‐endpoint path cover problem. Given a graph G and a subset ${\cal T}$ of k vertices of V ( G ), a k ‐fixed‐endpoint path cover of G with respect to ${\cal T}$ is a set of vertex‐disjoint paths ${\cal P}$ that covers the vertices of G such that the k vertices of ${\cal T}$ are all endpoints of the paths in ${\cal P}$ . The k ‐fixed‐endpoint path cover problem is to find a k ‐fixed‐endpoint path cover of G of minimum cardinality; note that, if ${\cal T}$ is empty, that is, k = 0, the stated problem coincides with the classical path cover problem. We show that the k ‐fixed‐endpoint path cover problem can be solved in linear time on the class of cographs. More precisely, we first establish a lower bound on the size of a minimum k ‐fixed‐endpoint path cover of a cograph and prove structural properties for the paths of such a path cover. Then, based on these properties, we describe an algorithm which, for a cograph G on n vertices and m edges, computes a minimum k ‐fixed‐endpoint path cover of G in linear time, that is, in O ( n + m ) time. The proposed algorithm is simple, requires linear space, and also enables us to solve some path cover related problems, such as the 1HP and 2HP, on cographs within the same time and space complexity. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 231–240 2007