Edge Completion Sequences for Classes of Chordal Graphs.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1995
- Accession Number
- ADA302986
Entities
People
- Richard M. Odom
Organizations
- Naval Postgraduate School