版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:National Taiwan University Taipei10617 Taiwan National Taiwan Ocean University Keelung20224 Taiwan
出 版 物:《arXiv》 (arXiv)
年 卷 期:2024年
核心收录:
摘 要: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.