处理带有时间信息的图（时序图）在实际场景中日益重要。本文聚焦于利用增量最小生成树（MST）来高效解决时序图相关的应用问题。\n\n第一项贡献是系统化地阐述了大量时序图处理的设置‑问题组合如何通过增量 MST 获得解，并给出相应的理论保证。尽管该问题重要，却存在理论与实践的显著差距：传统数据结构如 link‑cut tree 虽然在渐进复杂度上表现优异，却在真实数据上表现不佳；而现有的实用方案缺乏非平凡的理论界限。\n\n第二项也是核心贡献是提出了一系列在理论与实践上均高效的增量 MST 算法。我们设计的 AM‑tree 数据结构在时序图处理的理论界限上与 link‑cut tree 等价，同时在实验中展现出强劲的实际性能。实验结果表明，AM‑tree 在更新操作上比 link‑cut tree 快 7.8‑11 倍，在查询操作上快 7.7‑13.7 倍，并且在多数基准上能够匹配或超越现有的实用方案。\n\n实验设置包括合成数据和真实时序网络，评估指标覆盖更新时延、查询时延以及整体吞吐量。\n\n结论：AM‑tree 通过兼顾理论最优性和实际效率，为时序图的增量 MST 计算提供了可行且高效的实现路径。\n\n点评