An O(nlogn) algorithm for finding minimal path cover in circular-arc graphs

摘要

Whether there exists a polynomial algorithm for the minimal path cover problem in circular-arc graphs remains open. In this paper, we present a polynomial time algorithm for finding a minimal path cover for a set of n arcs in a circular-arc model. Our algorithm takes &Ogr;(nlogn) time.