MINIMIZING ELIMINATION TREE HEIGHT CAN INCREASE FILL MORE THAN LINEARLY

Authors
ASPVALL B
Citation
B. Aspvall, MINIMIZING ELIMINATION TREE HEIGHT CAN INCREASE FILL MORE THAN LINEARLY, Information processing letters, 56(2), 1995, pp. 115-120
Citations number
7
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
56
Issue
2
Year of publication
1995
Pages
115 - 120
Database
ISI
SICI code
0020-0190(1995)56:2<115:METHCI>2.0.ZU;2-0
Abstract
We show that there exist chordal graphs for which any elimination orde r corresponding to a minimum height elimination tree produces a non-li near amount of fill. The result implies that a conjecture by J.R. Gilb ert regarding the amount of fill in minimum height elimination trees d oes not hold for arbitrary graphs.