Accession Number : AD0722589

Title :   Two Algorithms for Finding the Absolute M-Center 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 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)

Descriptors :   (*GRAPHICS, ALGORITHMS), (*OPERATIONS RESEARCH, NETWORKS), ITERATIONS, SET THEORY, THEOREMS, THESES

Subject Categories : Theoretical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE