A faster implementation of a parallel tree contraction scheme and its application an distance-hereditary graphs

We consider a parallel tree contraction scheme which in each contraction ph ase removes leaves and nodes in the maximal chains. Let T(n) and P(n) denot e the time and processor complexity required Co compute the all nearest sma ller values (ANSV) and the minimum of n values for input elements drawn fro m the integer domain [1...n]. In is paper, we give a faster implementation of the tree contraction scheme which takes O(log n . T(n)) time using P(n) processors on an arbitrary CRCW PRAM. The current best results of T(n) and P(n) are O(log log log n) and O(n/log log log n), respectively. To our know ledge, the previously best known implementation needs O(log(2) n) time usin g O(n/log n) processors on an EREW PRAM. The faster parallel implementation of the tree contraction scheme may be of interests by itself. We then show the above scheme can be utilized to solve problems on distance-hereditary graphs. We provide a data structure to represent a connected distance-hered itary graph in the form of a rooted tree. By applying the above tree contra ction scheme on our data structure together with graph theoretical properti es, we solve the problems of finding a minimum connected gamma-dominating s et and finding a minimum gamma-dominating clique on a distance-hereditary g raph in O(log n . T(n)) time using O(P(n) + (n + m)/T(n)) processors on an arbitrary CRCW PRAM, where n and nz are the number of vertices and edges of the given graph, respectively. The above result implies several other prob lems related to the minimum gamma-dominating clique problem can be solved w ith the same parallel complexities, (C) 2000 Academic Press.