2024/11/29 by Ta-Yu Mu, Mu, Ta-Yu, Ching‐Chi Lin +1
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2411.19476
The domination problem and its variants represent a classical domain within algorithmic graph theory. Among these variants, the paired-domination problem holds particular prominence due to its real-world implications in security and surveillance domains. Given an input graph G, the paired-domination problem involves identifying a minimum dominating set D that induces a subgraph of G with a perfect matching. Lin et al.~[Paired-domination problem on distance-hereditary graphs, Algorithmica, 2020] previously presented a solution to this problem with a time complexity of O(n2). This paper significantly enhances their findings by introducing an O(n+m)-time algorithm. Furthermore, the time complexity of this algorithm can be reduced to O(n) when provided with a decomposition tree for the graph G.