The optimal path cover problem is to find a minimum number of vertex disjoint paths which together cover all the vertices of the graph. In this paper, we present linear-time algorithms for the optimal path cover problem for the class of block graphs and bipartite permutation graphs. © 1993.

Ravi Shanmuga Sundaram

Karan Sher Singh

Chandrasekharan Pandu Rangan

Algorithms

Graph theory

BIPARTITE PERMUTATION GRAPHS

BLOCK GRAPHS

Linear-time algorithms

OPTIMAL PATH COVER PROBLEM

VERTEX DISJOINT PATHS

Optimization

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Optimal path cover problem on block graphs and bipartite permutation graphs

Theoretical Computer Science

A path cover of a graph G is a set of vertex-disjoint paths that cover all the vertices of G. An optimal path cover of G is a path cover of minimum cardinality. This problem is known to be NP-complete for arbitrary graphs. We present a linear algorithm for this problem on interval graphs. Given the adjacency lists of an interval graph with n vertices and m edges, our algorithm runs in O(m+n) time. © 1990.

Journal	Theoretical Computer Science
ISSN	03043975
Open Access	Yes