Toward Characterization of Perfect Elimination Digraphs
Loren Haskins, Donald J. Rose · SIAM Journal on Computing · 1973
Perfect elimination digraphs arise in the study of Gaussian elimination on sparse linear systems. With a view toward numerical computational complexity we show four conditions (C1–C4) to be necessary for the perfect elimination property. The sufficiency of C1 is shown in general and the sufficiency of C2–C4 is shown in the symmetric case. The equivalence of C1–C3 is conjectured.