A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
Peng Li, Yaokun Wu · SIAM Journal on Discrete Mathematics · 2017
Let $G$ be an interval graph and take one of its vertices $x$. Can we find in linear time a minimum number of vertex disjoint paths of $G$ which cover the vertex set of $G$ and have $x$ as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches.