A practical algorithm for making filled graphs minimal
Jean R. S. Blair, Pinar Heggernes, Jan Arne Telle · Theoretical Computer Science · 2001
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.