CMU-CS-97-133Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-97-133
Claudson Bornstein, Bruce Maggs, Gary Miller, Ramomoorthi Ravi* May 1997
Keywords: Linear fill, height, parallel, interval graphs,
chordal graphs, gaussian elimination
O(m), and work at most
O(W, where ^{*}(G))W is the
minimum possible work over all elimination orderings for ^{ * }(G)G.
Experimental results show that when applied after some other heuristic,
the increase in work and fill is usually small. In some instances the
algorithm obtains an ordering that is actually better, in terms of work
and fill, than the original one. We also present an algorithm that
produces an ordering with a factor of log n less height, but
with a factor of O(\/log n) more fill.
34 pages
*Graduate School of Industrial Administration,
Carnegie Mellon University
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |