当支配性何时重要？基于结构和计算方法研究几何网络中的生成树与支配树 帕布罗·阿达斯梅（Pablo Adasme）

《Mathematics》：When Does Domination Matter? A Structural and Computational Study of Spanning and Dominating Trees in Geometric Networks Pablo Adasme

　　

摘要

在几何通信网络中，骨干网络只有在构建成本低廉且同时足够接近其必须服务的需求点时才有用。本文研究了一种几何通信网络中的骨干网络设计问题，该问题明确考虑了连接性和用户覆盖范围之间的权衡。本文考虑了两种经典的组合优化范式：最小生成树（MST）和支配树（DT）。最小生成树旨在实现低成本的连接性，而支配树则确保每个节点要么属于骨干网络，要么与某个活跃的骨干网络节点相邻。为了在统一框架内比较这两种范式，本文提出了一个混合整数优化模型，以平衡骨干网络建设和用户分配的成本。本文开发了三种精确的建模方法：MTZ、单流模型和割集模型。特别是，单流模型通过有效的不等式和考虑根节点的连接性割得到了增强。对于较大的 instances，精确方法还结合了局部分支数学启发式算法。最后，本文提供了关于计算复杂性、建模结构以及MST和DT模型之间支配关系的理论结果。计算实验表明，单流模型在可扩展性方面表现最佳。此外，针对通信半径和权重参数的敏感性分析揭示了一个结构转变：随着网络密度的增加或目标更倾向于覆盖范围，MST和DT的解决方案趋于收敛。这些结果为确定何时需要施加支配约束以及何时更简单的生成树设计已经能够捕捉到相关结构提供了具体的方法。