Fast parallel algorithms for chordal graphs

1987/01/01 by Joseph Naor, Moni Naor, Alejandro A. Schäffer · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs #Chordal graph #Interval graph #Graph coloring #Computer science #Split graph #Intersection (aeronautics) #Algorithm #Treewidth #Combinatorics #Indifference graph #Mathematics #Graph #Discrete mathematics #Pathwidth #Theoretical computer science #1-planar graph #Line graph

paper · pdf · doi:10.1145/28395.28433

openalex publication_date 1987/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We present an NC algorithm for recognizing chordal graphs, and we present NC algorithms for finding the following objects on chordal graphs: all maximal cliques, an intersection graph representation, an optimal coloring, a perfect elimination scheme, a maximum independent set, a minimum clique cover, and the chromatic polynomial. The well known polynomial algorithms for these problems seem highly sequential, and therefore a different approach is needed to find parallel algorithms.

Citations

• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Normal hypergraphs and the perfect graph conjecture
• A taxonomy of problems with fast parallel algorithms
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Incidence matrices and interval graphs

Cited by

• Chromatic polynomial [wikipedia]