The parallel complexity of elimination ordering procedures

DOI10.1007/3-540-57899-4_55zbMath1528.68284OpenAlexW1799517289MaRDI QIDQ6143979

Elias Dahlhaus

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57899-4_55

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of recognizing perfectly orderable graphs
• Characterizations of strongly chordal graphs
• On the semi-perfect elimination
• Doubly lexical ordering of dense 0--1 matrices
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• 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
• Doubly Lexical Orderings of Matrices
• Four classes of perfectly orderable graphs
• Three Partition Refinement Algorithms
• An O(logn) parallel connectivity algorithm
• Algorithmic Aspects of Vertex Elimination on Graphs
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• Constructing a Maximal Independent Set in Parallel
• An upper bound for the chromatic number of a graph and its application to timetabling problems

This page was built for publication: The parallel complexity of elimination ordering procedures