Efficient Parallel Algorithms for Chordal Graphs

The author gives efficient parallel algorithms for recognizing chordal graphs, finding a maximum clique and a maximum independent set in a chordal graph, finding an optimal coloring of a chordal graph, finding a breadth-first search tree and a depth-first search tree of a chordal graph, recognizing interval graphs, and testing interval graphs for isomorphism. The key to the results is an efficient parallel algorithm for finding a perfect elimination ordering. >

Authors

• Philip N. Klein

Keywords

• Parallel algorithms
• Tree graphs
• Testing
• Databases
• Polynomials
• Intelligent control
• Contracts
• Sun
• Efficient Algorithm
• Parallel Algorithm
• Graph Algorithms
• Chordal Graphs
• Efficient Parallel Algorithm
• Parallelization
• Independent Set
• Neighboring Nodes
• Linear Time
• Subtree
• Tree Search
• Recursive Algorithm
• Intermediate Number
• Depth-first
• Joining Tree
• Breadth-first Search
• Spanning Tree
• Crimson