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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1971
- Accession Number
- AD0742938
Entities
People
- Roderick William Lins
Organizations
- Naval Postgraduate School