ISSN:
1436-5057
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Diese Arbeit untersucht das folgende Optimierungsproblem: gegeben sei eine Menge von PunktenP i ,i=1,2, ...,n, in der Ebene, jeder mit Gewichtw i , und eine Kreisscheibe mit vorgegebenem Radius; finde eine Plazierung der Kreisscheibe, die die Summe der Gewichte aller überdeckten Punkte maximiert. Dieses Problem ist äquivalent zum folgenden Problem definiert für den Schnittgraphen vonn kongruenten gewichteten Kreisscheiben in der Ebene: bestimme eine Clique (die korrespondierenden Kreisscheiben haben einen nichtleeren gemeinsamen Durchschnitt), die die Summe der Gewichte maximiert. Wir präsentieren einenO (n 2)-Algorithmus für dieses Problem, was eine Verbesserung darstellt gegenüber dem besten bisher bekannten Algorithmus, der sortiert undO (n 2 logn) an Laufzeit benötigt.
Notes:
Abstract We consider the following circle placement problem: given a set of pointsp i ,i=1,2, ...,n, each of weightw i , in the plane, and a fixed disk of radiusr, find a location to place the disk such that the total weight of the points covered by the disk is maximized. The problem is equivalent to the so-called maximum weighted clique problem for circle intersection graphs. That is, given a setS ofn circles,D i ,i=1,2, ...,n, of the same radiusr, each of weightw i , find a subset ofS whose common intersection is nonempty and whose total weight is maximum. AnO (n 2) algorithm is presented for the maximum clique problem. The algorithm is better than a previously known algorithm which is based on sorting and runs inO (n 2 logn) time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238188
Permalink
