The M-center problem.

Download
Author
Lins, Roderick William
Date
1971-12Advisor
McMasters, Alan W.
Metadata
Show full item recordAbstract
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.
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
Locating absolute 2-centers of undirected graphs
Gillespie, Clark McKinley, Jr. (1968-12);This study analyzes the location of vertex and absolute 2-centers of an undirected graph. Under certain assumptions, these locations would be useful for determining the optimal positioning of emergency facilities such as ... -
Vortex flow in an actual gas.
Vickrey, William Clyde; Vickrey, William Clyde (Rensselaer Polytechnic Institute, 1948-05);Applications of the vortex have been used in engineering for many years. Since the recent publication of Rudolph Hilsch's work in Germany it is widely known that there is a transfer of energy from the center to the ... -
Competitive Weighted Matching in Transversal Matroids
Dimitrov, N. B.; Plaxton, C.G. (2010-09);Consider a bipartite graph with a set of left-vertices and a set of right-vertices. All the edges adjacent to the same left-vertex have the same weight. We present an algorithm that, given the set of right-vertices and the ...