A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
Glenn K. Manacher, Terrance A. Mankus · Networks · 2002
Abstract We exhibit an algorithm for finding a maximum independent set (MIS) for n presorted, unweighted circular arcs in time 0(n). Unlike previous algorithms, this is achieved by means of trivial postprocessing of the output of a straightforward algorithm for finding an MIS for a set of unweighted intervals. © 2002 Wiley Periodicals, Inc.