Please use this identifier to cite or link to this item:
標題: K-best Cuts for Circular-arc Graphs
作者: K.H.Tsai
關鍵字: Circular-arc graph;Interval graph;Facility location;Competitive;location;Maximum clique cover
出版社: Springer-Verlag
Project: Algorithmica, Volume�18, Issue�2, Page(s) �198-216.
Given a set ofn nonnegativeweighted circular arcs on a unit circle, and an integerk, thek Best Cust for Circular-Arcs problem, abbreviated as thek-BCCA problem, is to find a placement ofk points, calledcuts, 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, thek Best Cuts for Intervals (k-BCI) problem, inO(kn+n logn) time andO(kn) space using dynamic programming. The algorithm is then extended to solve a variation, called thek-restricted BCI problem, and the space complexity of thek-BCI problem can be improved toO(n). Based on these results, we then show that thek-BCCA problem can be solved inO(I(k,n)+nlogn) time, whereI(k, n) is the time complexity of thek-BCI problem. As a by-product, thek Maximum Cliques Cover problem (k>1) for the circular-arc graphs can be solved inO(I(k,n)+nlogn) time.
ISSN: 0178-4617
DOI: 10.1007/BF02526033
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.