Title:  k Best Cuts for Circular-Arc Graphs*


*Supported in part by the National Science Foundation
 under the Grants CCR-8901815, CCR-9309743 and INT-9207212,
 and by the Office of Naval Research under 
 the Grant No. N00014-93-1-0272.

K. H. Tsai
Institute of Information Science, 
Academia Sinica, 
Nankang, Taipei, Taiwan
e-mail: tsaikh@iis.sinica.edu.tw

and  
D. T. Lee 
Department of Electrical and Computer Engineering
Northwestern University, Evanston, Illinois 60208
e-mail: dtlee@ece.nwu.edu 

Abstract:

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, abbreviated as k-BCCA problem, is to find a placement 
of k points, called cuts, 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 using dynamic programming, 
the k Best Cuts for Intervals (k-BCI) problem in 
$(kn + n\log n) time and O(kn) space.  The algorithm is then 
extended to solve a variation, called the k-restricted BCI 
problem, and the space 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 the k-BCI problem.
As a by-product, the k Maximum Cliques Cover problem, (k>1) 
for the circular-arc graphs can be solved in O(I(k,n)+n\log n) 
time.

Key Words: Circular-arc graphs, Interval graphs, Facility location,
       Competitive location, Maximum clique cover.

Algorithmica, 18(2):198-216, June 1997.