A simple and fast parallel coloring for distance-hereditary graphs

In the literature, there are quite a few sequential and parallel algorithms to solve problems on distance-hereditary graphs. Two well-known classes of graphs, which contain trees and cographs, belong to distance-hereditary graphs. We consider the vertex-coloring problem on distance-hereditary graphs. Let T_d(|V|, |E|) and P_dd(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree representation of a distance-hereditary graph G=(V,E) on a PRAM model M_d. Our algorithm runs in O(T_d(|V|, |E|)+log|V|) time using O(P_d(|V|, |E|)+|V|/log|V|) processors on M_d. The best known result for constructing a decomposition tree needs O(log² |V|) time using O(|V|+|E|) processors on a CREW PRAM. If a decomposition tree is provided as input, we solve the problem in O(log |V|) time using O(|V|/log |V|) processors on an EREW PRAM. To the best of our knowledge, there is no parallel algorithm for this problem on distance-hereditary graphs.