The following technical report is available from http://aib.informatik.rwth-aachen.de:
An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs George B. Mertzios, Walter Unger AIB 2008-09
In this paper we consider the $k$-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a proper interval graph $G$ and a particular set $T$ of $k$ vertices, the goal is to compute a path cover of $G$ with minimum cardinality, such that the vertices of $T$ are endpoints of these paths. We propose an optimal algorithm for this problem with runtime $O(n)$, where $n$ is the number of intervals in $G$. This algorithm is based on the \emph{Stair Normal Interval Representation (SNIR) matrix} of proper interval graphs.