The Optimum Location of Multi-centres on a Graph

Abstract

The location of a number of service centres on a network (graph) in such a way so that every node (demand point) lies within a critical distance of at least one of the centres appears often in problems involving emergency services. When the number p of centres is fixed and what is required is their location so that this critical distance is the smallest possible, the resulting location is called "the absolute p-centre of the graph". This paper presents an iterative algorithm for finding absolute p-centres in general (weighted or unweighted) graphs. The algorithm is shown to be computationally efficient for quite large graphs. Results (computing times and numbers of iterations) are given for 15 test graphs varying in size from 10 to 50 nodes and from 20 to 120 links.