动态图最小生成树维护算法ContraMST：基于树收缩的批量更新并行优化框架

本文提出ContraMST算法框架，通过树收缩（tree contraction）机制构建层次化RC树结构，实现动态图最小生成树（MST）的高效批量维护。在GPU并行环境下，该框架对增量更新（IMB）、减量更新（DMB）和全动态混合更新（FDM）分别实现3.43×-7.31×加速，显著优于传统CPU并行重计算方法，为实时网络分析（如无线自组网MDT结构优化）提供关键技术支撑。

　　

Highlight

ContraMST通过多阶段边更新机制最小化冗余计算，结合GPU加速的Bor?ˉvka式初始化与CPU协调的细粒度更新引擎。特别地，优化变体FDM_V3采用基于分解的锁机制和优先级感知并发，将冗余并查集（union-find）操作从85K降至38K，显著提升高吞吐动态环境下的性能。

Related Work

现有动态MST算法如Eppstein的稀疏化（sparsification）框架虽理论高效，但难以适应现代并行环境。对比实验显示，传统方法如Zhou的动态Kruskal会产生2.3×冗余MST边重计算，而ContraMST通过架构感知设计提供异构系统下的实时解决方案。

Preliminaries

最小生成树（MST）问题要求无环连通图中权重最小的边子集（见图2）。经典算法包括Prim、Kruskal和Bor?ˉvka算法，而ContraMST创新性地将其扩展至动态场景。

Methodology

ContraMST采用增量批处理（IMB）、减量批处理（DMB）和全动态MST（FDM）三层架构：

• •

  IMB：通过局部性更新避免全图重计算

• •

  DMB：采用链接切割树（LC tree）识别阈值|E_s|≥TME的受影响子树

• •

  FDM_V3：在根节点级集成优先级队列与分解锁，实现线程安全的混合批处理

Evaluation

在配备NVIDIA A100 GPU的服务器上测试显示：

• 稀疏/稠密图分类基于顶点数(|V|)和边数(|E|)

• FDM_V3处理37.4亿边仅需2.5毫秒

Conclusion and Future Work

ContraMST在批更新场景下实现IMB 3.5×、DMB 5.1×、FDM 7.5×加速，其树收缩技术为动态图分析开辟新方向。未来将探索更复杂的图属性联合维护策略。