## Abstract

We consider the following circle placement problem: given a set of points p_{i}, i=1,2, ..., n, each of weight w_{i}, in the plane, and a fixed disk of radius r, 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 set S of n circles, D_{i}, i=1,2, ..., n, of the same radius r, each of weight w_{i}, find a subset of S whose common intersection is nonempty and whose total weight is maximum. An O (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 in O (n^{2} log n) time.

Original language | English (US) |
---|---|

Pages (from-to) | 1-16 |

Number of pages | 16 |

Journal | Computing |

Volume | 36 |

Issue number | 1-2 |

DOIs | |

State | Published - Mar 1 1986 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computational Theory and Mathematics