INDEPENDENT SETS IN CIRCULAR-ARC GRAPHS

This paper presents a linear time algorithm for the independent set pr oblem on circular-are graphs. previous algorithms for this problem hav e assumed that the input is a set of circular-arcs and solve the probl em in O(n) time. However, the fastest known algorithm for constructing the circular-are representation from a set of adjacency lists takes O (n(2)) time. We show that we can solve the problem in O(n + m) time, w hen we are given the circular-are graph as a set of adjacency lists. ( C) 1995 Academic Press, Inc.