Conditional Completion Algorithms for Classes of Chordal Graphs
Loading...
Authors
Odom, Richard M.
Rasmussen, Craig W.
Subjects
Advisors
Date of Issue
1996
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
If G = (F, E) i8 a 8irnple graph of order n and 8iz.e q, and if P is a property held
by C, Lhen a. P-compleLion 8equence for G is an ordering t 1 , e2 , ... , e("~)-q of Lhe edges of K,, - G
such that Ch= ( v, /",~ + u-~, e,) has propprty p for Pach k = 1: '.Z, ... ' (;) - q. \VP add thP stronp;ly
chordal graphs to Lhe 8el of dasse8 for which such 8equence8 are known Lo exisL, and 8how Lha.L ?completion
sequences for these and several other subclasses of the chordal graphs can be constructed
in polynomial time. In most cases we exploit the corresponding vertex elimination orderings.
Type
Description
Series/Report No
Department
Applied Mathematics
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.