Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/38294
DC FieldValueLanguage
dc.contributor.authorK.H.Tsaien_US
dc.contributor.authorD.T.Leeen_US
dc.date1997-06en_US
dc.date.accessioned2014-06-06T08:00:41Z-
dc.date.available2014-06-06T08:00:41Z-
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/11455/38294-
dc.description.abstractGiven 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.en_US
dc.language.isoen_USen_US
dc.publisherSpringer-Verlagen_US
dc.relationAlgorithmica, Volume�18, Issue�2, Page(s) �198-216.en_US
dc.subjectCircular-arc graphen_US
dc.subjectInterval graphen_US
dc.subjectFacility locationen_US
dc.subjectCompetitiveen_US
dc.subjectlocationen_US
dc.subjectMaximum clique coveren_US
dc.titleK-best Cuts for Circular-arc Graphsen_US
dc.typeJournal Articlezh_TW
dc.identifier.doi10.1007/BF02526033en_US
item.openairetypeJournal Article-
item.fulltextno fulltext-
item.grantfulltextnone-
item.languageiso639-1en_US-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.cerifentitytypePublications-
Appears in Collections:資訊科學與工程學系所
Show simple item record
 

Google ScholarTM

Check

Altmetric

Altmetric


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