The M-center problem.
Lins, Roderick William
McMasters, Alan W.
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
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 ...
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 ...
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 ...