摘要
A circular arc family F is a collection of arcs on a circle. A circular-arc graph is the intersection graph of an arc family. A Hamiltonian cycle (HC) in a graph is a cycle that passes through every vertex exactly once. This paper presents an $O(n2 \\\\\\\\\\\\\\\\log n)$ algorithm to determine whether a given circular-arc graph contains an HC. This algorithm is based on two subroutines for interval graphs: (i) a linear time greedy algorithm for the node disjoint path cover problem and (ii) a linear time HC algorithm. If the given graph does not contain an HC, this paper can produce a proof either through the deletion of an appropriate cutset or through the failure to obtain a specific type of HC.