Popis: |
The study of domination problem and its variants is a classical area in algorithmic graph theory. One of the most famous variants of the domination problem is paired-domination as it has practical applications in security and surveillance services. Given a graph G, the paired-domination problem on G is to determine a minimum dominating set D such that the subgraph of G induced by D has a perfect matching. Lin et al. [Paired-domination problem on distance-hereditary graphs, Algorithmica, 2020] showed that the problem could be solved in O(n2) time. In this paper, we strengthen their results by providing an O(n+m)-time algorithm. Moreover, the algorithm can be completed in O(n) time if a decomposition tree of G is given. |