有向图连通支配集求解算法研究

"这篇论文主要研究了有向图的连通支配集问题，这是一个在实际应用中具有重要性的网络设计和电路布线问题。由于连通支配集问题在无向图中已被证明为NP完全问题，因此作者将研究扩展到了有向图领域，这涉及到更多的组合数、非对称的可达性以及可能不存在连通支配集的情况。论文提出了有向图中节点支配关系的定义，并定义了有向图连通支配集问题。" 在论文中，作者首先指出了有向图与无向图在连通支配集问题上的差异，如有向图的边具有方向性，导致节点间的可达性不对称，以及连通支配集在非强连通有向图中可能不存在。鉴于此，他们提出了适应有向图的支配关系和连通支配集的定义。 接着，论文介绍了已有的无向图连通支配集问题的解决方法，包括确定性和近似算法。其中，确定性算法通过参数算法技术实现了时间复杂度为O(1.9407n)的改进，而近似算法则分为两种策略：一种是从单个节点出发逐步扩展成连通集合，另一种则是先找到一个较小的支配集，再通过添加节点使之连通。 针对有向图的连通支配集问题，论文提出了规约规则来降低问题的复杂度，这些规约规则能够减少原问题的规模。之后，作者设计了一种近似算法在规约后的有向图上寻找连通支配集。在得到初步结果后，他们还利用规约规则带来的特性，设计了优化规则对求得的连通支配集进行进一步的缩减，以达到更小的规模。 通过在不同模型的随机图上进行的模拟实验，这些规约规则和优化算法的有效性得到了验证。这意味着这些方法对于解决实际中的有向图连通支配集问题提供了有力的工具，特别是在网络设计和电路布局等领域，能够帮助找到更高效的解决方案。 这篇论文深入探讨了有向图连通支配集问题，提出了一套包括规约、近似算法和优化在内的综合方法，为处理这一复杂问题提供了新的思路和实用的计算策略。