K-BEST CUTS FOR CIRCULAR-ARC GRAPHS

Given a set of n nonnegative weighted circular arcs on a unit circle, and an integer k, the k Best Cuts for Circular-Arcs problem, abbreviat ed as the K-BCCA problem, is to find a placement of k points, called c uts, on the circle such that the total weight of the arcs that contain at least one cut is maximized. We first solve a simpler version. the k Best Curs for Intervals (k-BCI) problem, in O(kn + n log n) time and O (kn) space using dynamic programming. The algorithm is then extende d to solve a variation, called the k-restricted BCI problem, and the s pace complexity of the k-BCI problem can be improved to O(n). Based on these results, we then show that the k-BCCA problem can be solved in O(I(k, n) + n log n) time, where I (k, n) is the time complexity of th e k-BCI problem. As a by-product, the k Maximum Cliques Cover problem (k > I) for the circular-are graphs can be salved in O(I(k, n) + n log n) time.