咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Optimal Algorithm for Paired-D... 收藏
arXiv

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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分