Paired-Domination Problem on Distance Hereditary Graphs.
Journal
New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Yunlin, Taiwan, December 20-22, 2018, Revised Selected Papers
Pages
495-502
Date Issued
2018
Author(s)
Abstract
A paired-dominating set of a graph G is a dominating set S of G such that the subgraph of G induced by S has a perfect matching. In [Paired domination in graphs, Networks, 32:199–206, 1998], Haynes and Slater introduced the concept of paired-domination and showed that the problem of determining minimum paired-dominating sets is NP-complete on general graphs. Ever since then many algorithmic results are studied on some important classes of graphs. In this paper, we extend the results by providing an O(n2) -time algorithm on distance-hereditary graphs.
Type
conference paper