A Linear Reordering Algorithm for Parallel Pivoting of Chordal Graphs
Joseph W. H. Liu, Andranik Mirzaian · SIAM Journal on Discrete Mathematics · 1989
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
SIAM Journal on Discrete Mathematics · Society for Industrial and Applied Mathematics · article · 1989
Abstract
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.
Open the resolved locator · 10.1137/0402011
Metadata licence: OpenAlex metadata (CC0)