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