Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
From MaRDI portal
Publication:2378540
DOI10.1016/j.tcs.2008.09.059zbMath1155.68088OpenAlexW1988291464MaRDI QIDQ2378540
Pinar Heggernes, Anne Berry, Geneviève Simonet, Elias Dahlhaus
Publication date: 8 January 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.059
Related Items
Minimum Average Distance Clique Trees, Bayes linear analysis for ordinary differential equations, Treewidth computations. I: Upper bounds, A survey of direct methods for sparse linear systems, Fast minimal triangulation algorithm using minimum degree criterion
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- A practical algorithm for making filled graphs minimal
- Maximum cardinality search for computing minimal triangulations of graphs
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- The Elimination form of the Inverse and its Application to Linear Programming
- Minimal Orderings Revisited
- The Use of Linear Graphs in Gauss Elimination
- Representation of a finite graph by a set of intervals on the real line
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Parallel Merge Sort
- The Evolution of the Minimum Degree Ordering Algorithm
- An O(logn) parallel connectivity algorithm
- Computing the Minimum Fill-In is NP-Complete
- Algorithmic Aspects of Vertex Elimination on Graphs
- Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
- An Approximate Minimum Degree Ordering Algorithm
- Graph-Theoretic Concepts in Computer Science