The M-center problem.

Abstract

Solution algorithms are presented for the vertex m-center and the absolute m-center problem. Both algorithms use partitioning techniques The algorithms use special properties of the max-min node to test for optimality. The vertex m-center algorithm establishes an order among all partitions of a graph according to the smallest vertex m-radius each partition can have. It then directs one to calculate the vertex m-radii only for those partitions which can provide a minimal vertex m-radius. The absolute m-center algorithm establishes an initial solution which may not be optimal. Other partitions are then tested against this solution to determine whether or not they provide a better solution. A point is reached at which no untested partition can improve the extant solution and the algorithm terminates.