A clique tree algorithm for partitioning a chordal graph into transitive subgraphs

DOI10.1016/0024-3795(95)00092-6zbMath0827.05057OpenAlexW2059241685MaRDI QIDQ1894513

Alex Pothen, Xiaoqing Yuan, Barry W. Peyton

Publication date: 6 September 1995

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(95)00092-6

zbMATH Keywords

chordal graphclique tree algorithmchordal graph elimination orderinglinear time greedy algorithmparallel sparse triangular solution

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A survey of direct methods for sparse linear systems, Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs, Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Topics on perfect graphs
• Reordering sparse matrices for parallel elimination
• Trivially perfect graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Graph theory and sparse matrix computation. Proceedings of a workshop that was an integral part of the 1991-92 IMA program on Applied linear algebra, Minneapolis, MN (USA)
• Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• Power of Natural Semijoins
• A Fast Reordering Algorithm for Parallel Sparse Triangular Solution
• Stability of the Partitioned Inverse Method for Parallel Solution of Sparse Triangular Systems
• Algorithmic Aspects of Neighborhood Numbers
• Optimal Parallel Solution of Sparse Triangular Systems