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.
Approved for public release; distribution is unlimited
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 ...