請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38389
標題: On a Circle Placement Problem
作者: B.M.Chazelle
D.T.Lee
出版社: Springer-Verlag
摘要: 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.
URI: http://hdl.handle.net/11455/38389
ISSN: 0010-485X
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。