
Accession Number : AD0722589
Title : Two Algorithms for Finding the Absolute MCenter of a Graph.
Descriptive Note : Master's thesis,
Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CALIF
Personal Author(s) : Reed,John Jesse
Report Date : MAR 1971
Pagination or Media Count : 75
Abstract : Two algorithms for finding the absolute mcenter are developed, combining the ideas of Hakimi, Gillespie, and Rosenthal and Smith. The first algorithm developed is essentially a handcomputational method. It is based on partitioning the graph into m subgraphs centered on the elements of the vertex mcenter. 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 mcenters of a graph if each of these mcentral paths passes through an element of the vertex mcenter. The second algorithm is an iterative search of all possible sets of m edges on which the absolute mcenter 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 RosenthalSmith algorithm in handling peripheral vertices. (Author)
Descriptors : (*GRAPHICS, ALGORITHMS), (*OPERATIONS RESEARCH, NETWORKS), ITERATIONS, SET THEORY, THEOREMS, THESES
Subject Categories : Theoretical Mathematics
Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE