Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs

DOI10.1016/0898-1221(95)00006-KzbMath0815.68059OpenAlexW2073473571MaRDI QIDQ1842819

Stavros D. Nikolopoulos, Stylianos D. Danielopoulos

Publication date: 20 April 1995

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(95)00006-k

zbMATH Keywords

triangulated graphlexicographic searchperfect elimination schemesperfect Gaussian elimination

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (2)

Recognizing cographs and threshold graphs through a classification of their edges ⋮ Optimal gray-code labeling and recognition algorithms for hypercubes

Cites Work

• Unnamed Item
• Chordal graph recognition is in NC
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• Parallel computation and conflicts in memory access
• Infinite triangulated graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Triangulated graphs and the elimination process
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
• Algorithmic Aspects of Vertex Elimination on Graphs
• Optimal bounds for decision problems on the CRCW PRAM
• Implementation of simultaneous memory address access in models that forbid it

This page was built for publication: Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs