Efficient parallel algorithms on chordal graphs with a sparse tree representation

Chordal graphs are nothing else than intersection graphs of subtrees of a tree. We present optimal and almost-optimal algorithms for certain graph problems if the input graph is given by a collection of subtrees of a tree and the subtrees are given by their leaves. This generalizes results of Olariu, Schwing and Zhang (1992), Kim (1989) and Chen (1992) concerning the parallel complexity of problems on interval graphs provided the interval structure is given. In particular, we consider the problems to find a breadth-first search tree, to find a depth-first search tree, to find a minimum covering of the vertices by cliques, and to find a minimum coloring.<
>