NC algorithms for recognizing chordal graphs and k trees
N. Chandrasekharan, S. S. Iyengar · IEEE Transactions on Computers · 1988
The authors present parallel algorithms for recognizing the chordal graphs and k trees. Under the PRAM (parallel random-access-machine) model of computation with concurrent reading and writing allowed, these algorithms take O(log n) time and require O(n/sup 4/) processors. The algorithms have a better processor bound than an independent result by A. Edenbrandt (1985) for recognizing chordal graphs in parallel using O(n/sup 3/m) processors.>