An efficient parallel algorithm for the efficient domination problem on distance-hereditary graphs |
| |
Authors: | Sun-yuan Hsieh |
| |
Affiliation: | Dept. of Comput. Sci. & Inf. Eng., Nat. Cheng Kung Univ., Tainan; |
| |
Abstract: | In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log/sup 2/ n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM. |
| |
Keywords: | |
|
|