Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs

作     者：Mu, Ta-Yu Lin, Ching-Chi 

作者机构：National Taiwan University Taipei10617 Taiwan National Taiwan Ocean University Keelung20224 Taiwan 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Consensus algorithm 

摘      要：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. Copyright © 2024, The Authors. All rights reserved.