The M-center problem.
Loading...
Authors
Lins, Roderick William
Subjects
m-center
vertex m-center
absolute m-center
partition
vertex m-center
absolute m-center
partition
Advisors
McMasters, Alan W.
Date of Issue
1971-12
Date
December 1971
Publisher
Monterey, California ; Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Operations Research and Administrative Sciences
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.