An efficient parallel strategy for the perfect domination problem on distance-hereditary graphs |
| |
Authors: | Sun-Yuan Hsieh |
| |
Affiliation: | (1) Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, Ta-Hsueh Road, Tainan, 701, Taiwan |
| |
Abstract: | A graph is distance-hereditary if the distance stays the same between any of two vertices in every connected induced subgraph containing both. Two well-known classes of graphs, trees and cographs, both belong to distance-hereditary graphs. In this paper, we first show that the perfect domination problem can be solved in sequential linear-time on distance-hereditary graphs. By sketching some regular property of the problem, we also show that it can be easily parallelized on distance-hereditary graphs. |
| |
Keywords: | Parallel algorithms Parallel random access machine (PRAM) Distance-hereditary graphs The perfect domination problem |
本文献已被 SpringerLink 等数据库收录! |
|