Conditional Completion Algorithms for Classes of Chordal Graphs
Odom, Richard M.
Rasmussen, Craig W.
MetadataShow full item record
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.