A practical algorithm for making filled graphs minimal

For an arbitrary filled graph G + of a given original graph G, we consider the problem of removing fill edges from G + in order to obtain a graph M that is both a minimal filled graph of G and a subgraph of G +. For G + with f fill edges and e original edges, we give a simple O(f(e+f)) algorithm which solves the problem and computes a corresponding minimal elimination ordering of G. We report on experiments with an implementation of our algorithm, where we test graphs G corresponding to some real sparse matrix applications and apply well-known and widely used ordering heuristics to find G +. Our findings show the amount of fill that is commonly removed by a minimalization for each of these heuristics, and also indicate that the runtime of our algorithm on these practical graphs is better than the presented worst-case bound.

Authors

• Jean R.S. Blair
• Pinar Heggernes
• Jan Arne Telle

Keywords

No keywords are indexed for this paper.