Optimal parallel colouring algorithms for totally decomposable graphs

Abstract

Call a graph G totally decomposable if there exists a unique rooted tree T(G) whose leaves correspond to the vertices of G and whose internal nodes correspond to certain graph operations. As it turns out, totally decomposable graphs are extremely attractive from the computational point of view since many notoriously difficult problems on arbitrary graph become tractable for this class. We present optimal cost parallel colouring algorithms for a vast class of totally decomposable graphs. With an n-vertex graph represented by its parse tree input, all our algorithms run in O(n/p + log n) time using p (p ≤ n log n) processors in the EREW-PRAM model.

Keywords:

• Totally decomposable graphs
• networks
• local density
• list ranking
• tree contraction
• parallel algorithms
• EREW-PRAM

C.R. CATEGORIES::

• G.1.0
• G.2.2

^†This author was supported, in part, by the NSF grant CCR-8909996.

^†This author was supported, in part, by the NSF grant CCR-8909996.

Notes

^†This author was supported, in part, by the NSF grant CCR-8909996.