Tech Report CS-91-48

Parallel Algorithms for Chordal Graphs

Philip Klein

July 1991 (replaces CS-91-33)


This paper is a version of a chapter to be included in {\em The Synthesis of Parallel Algorithms}, edited by John H. Reif. We describe algorithms, both sequential and parallel, for {\em chordal graphs}, a class of graphs including {\em interval graphs}. We start by defining the notions of an interval graph, a chordal graph, a perfect elimination ordering, and an elimination tree. We illustrate these notions by showing how the elimination ordering can be used to solve optimization problems sequentially on chordal graphs. Then we show how the sequential solutions may be efficiently carried out in parallel. The sequential algorithms are due to Gavril. The parallel algorithms are due to Naor, Naor, and Sch\"affer, and to Klein.

The key to these efficient sequential and parallel solutions is finding a perfect elimination ordering. In the latter part of this chapter, we define a framework for finding an elimination ordering by successive refinement. Working within this framework, we explain the sequential algorithm due to Rose, Tarjan, and Lueker. Then we describe the parallel algorithm due to Klein.

(complete text in pdf)