Title :
Efficient parallel algorithms for chordal graphs
Author :
Klein, Philip N.
Author_Institution :
Harvard Univ., Cambridge, MA, USA
Abstract :
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
Keywords :
graph colouring; parallel algorithms; breadth-first search tree; chordal graphs; depth-first search tree; elimination ordering; interval graphs; isomorphism; maximum clique; maximum independent set; optimal coloring; parallel algorithms; Contracts; Databases; Intelligent control; Parallel algorithms; Polynomials; Sun; Testing; Tree graphs;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21933
