A Linear Reordering Algorithm for Parallel Pivoting of Chordal Graphs
Joseph W. H. Liu, Andranik Mirzaian · SIAM Journal on Discrete Mathematics · 1989
This paper provides an efficient algorithm for generating an ordering suitable for the parallel elimination of nodes in chordal graphs. The time complexity of the reordering algorithm is shown to be linear in the size of the chordal graph. The basic parallel pivoting strategy is originally by Jess and Kees [IEEE Trans. Comput., C-31 (1982), pp. 231–239]. The relevance of the reordering to parallel factorization of sparse matrices (not necessarily chordal) is also discussed.