Practical parallel algorithms for chordal graphs

Given a chordal graph, parallel solutions are given for finding the set of maximal cliques, a perfect elimination ordering and a minimum coloring. The solutions to these problems have a variety of applications. While other parallel solutions to these problems exist, this paper presents algorithms that use resources more efficiently and involve less total computation and so have a faster running time on a fixed number of processors. Questions of processor grain size, communication costs, algorithm costs and possible pipelining benefits are also discussed.