Minimal orderings revisited (Q2784346)

A new algorithm is derived for computing better minimal orderings and which is more efficient than the algorithm of \textit{D. J. Rose, R. E. Tarjan} and \textit{G. S. Lueker} [SIAM J. Comput. 5, 266-283 (1976; Zbl 0353.65019)], while computing minimum ordering is NP-complete. The algorithm begins with any initial ordering and then refines it until a minimal ordering is obtained by generating a sequence of reorderings, each removing additional fill from the current fill graph until a minimal chordal supergraph is obtained. Concepts and structures from sparse Choleski factorization have been used, including elimination trees, supernodes, supernodal elimination trees topological orderings, minimum degree algorithm and column counts. Experimental results are presented for several initial orderings and the algorithm is most efficient when the initial ordering is close to minimal.