Accession Number : ADA302986

Title :   Edge Completion Sequences for Classes of Chordal Graphs.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Odom, Richard M.

PDF Url : ADA302986

Report Date : JUN 1995

Pagination or Media Count : 52

Abstract : Given an incomplete graph G = (V, E) of order n and size m and possessing some property P, a P-Completion sequence for G is a sequence e1,,,,,,es of edges, where s = (n2) - m, with the property that if Go = G then (1) Gi is obtaIned from G(i-1) by insertion of exactly one edge and (2) Gi has property P for each 1<i<s. The O(n2) algorithm for constructing chordal completion sequences depends on a perfect elimination ordering a. We show that completion sequences can be generated for several subclasses of chordal graphs using a generic algorithm, of which the chordal completion algorithm is a special case, with the input being a graph from one of the subclasses and a specific ordering of the vertices that characterizes the subclass. We include a discussion of the strong elimination ordering for strongly chordal graphs, the interval elimination ordering for interval graphs and the bicompatible ordering for unit interval graphs. We define a threshold elimination ordering and then prove that a graph G is a threshold graph if and only if G has a threshold elimination ordering. We show that completion sequences exist for strongly chordal graphs. Finally, we prove that completion sequences for strongly chordal, interval, unit interval, split and threshold graphs can be constructed in O(n2) time. (AN)

Descriptors :   *GRAPHS, *SEQUENCES(MATHEMATICS), ALGORITHMS, EDGES, THESES, COMBINATORIAL ANALYSIS, APPLIED MATHEMATICS, SET THEORY, HAMILTONIAN FUNCTIONS, INTERVALS, POINTS(MATHEMATICS).

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE