Two Algorithms for Finding the Absolute M-Center of a Graph.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1971
- Accession Number
- AD0722589
Entities
People
- John Jesse Reed
Organizations
- Naval Postgraduate School