๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the rectangular p-center problem

โœ Scribed by Zvi Drezner

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
322 KB
Volume
34
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

โœฆ Synopsis

The p-center problem involves finding the best locations for p facilities such that the furthest among n points is as close as possible to one of the facilities. Rectangular (sometimes called rectilinear, Manhattan, or 1,) distances are considered. An O ( n ) algorithm for the 1-center problem, an O ( n ) algorithm for the 2-center problem, and an O ( n logn) algorithm for the 3-center problem are given. Generalizations to general p-center problems are also discussed.

๐Ÿ“œ SIMILAR VOLUMES

A vertex-closing approach to the p-cente
A vertex-closing approach to the p-center problem
โœ Joseph S. Martinich ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 980 KB

This article uses a vertex-closing approach to investigate the p-center problem. The optimal set of vertices to close are found in imbedded subgraphs of the original graph. Properties of these subgraphs are presented and then used to characterize the optimal solution, to establish a priori upper and