An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph

DOI10.1016/0304-3975(94)90250-XzbMath0938.68958MaRDI QIDQ1341730

Elias Dahlhaus, Marek Karpinski

Publication date: 15 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (3)

Minimal triangulations of graphs: a survey ⋮ Minimal elimination of planar graphs ⋮ Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Decomposition by clique separators
• Simplicial decompositions of graphs - some uniqueness results
• Chordal graph recognition is in NC
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• An improved parallel algorithm that computes the BFS numbering of a directed graph
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Separator Theorem for Chordal Graphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A taxonomy of problems with fast parallel algorithms
• An Efficient Parallel Biconnectivity Algorithm
• Fast Parallel Algorithms for Chordal Graphs
• Parallel Prefix Computation
• An O(logn) parallel connectivity algorithm
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• Parallelism in random access machines
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph