EFFICIENT PARALLEL ALGORITHMS FOR CHORDAL GRAPHS

Authors
KLEIN PN
Citation
Pn. Klein, EFFICIENT PARALLEL ALGORITHMS FOR CHORDAL GRAPHS, SIAM journal on computing, 25(4), 1996, pp. 797-827
Citations number
44
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
25
Issue
4
Year of publication
1996
Pages
797 - 827
Database
ISI
SICI code
0097-5397(1996)25:4<797:EPAFCG>2.0.ZU;2-1
Abstract
We give the first efficient parallel algorithms for recognizing chorda l 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 chorda l graph, recognizing interval graphs, and testing interval graphs for isomorphism. The key to our results is an efficient parallel algorithm for finding a perfect elimination ordering.