Two Algorithms for Finding the Absolute M-Center of a Graph.
NAVAL POSTGRADUATE SCHOOL MONTEREY CALIF
Pagination or Media Count:
Two algorithms for finding the absolute m-center are developed, combining the ideas of Hakimi, Gillespie, and Rosenthal and Smith. The first algorithm developed is essentially a hand-computational method. It is based on partitioning the graph into m subgraphs centered on the elements of the vertex m-center. The minimum distance tree rooted on each element of the vertex m center is then formed and modified to yield the central path and thus the absolute center of each subgraph. This algorithm will give the absolute m-centers of a graph if each of these m-central paths passes through an element of the vertex m-center. The second algorithm is an iterative search of all possible sets of m edges on which the absolute m-center may be located. It is less efficient than the algorithm of Rosenthal and Smith when m 1, but appears to be more efficient for m 1. It does eliminate the problems encountered by the Rosenthal-Smith algorithm in handling peripheral vertices. Author
- Theoretical Mathematics
- Operations Research