Scholarlink

<p>The minimum spanning tree (MST) problem is a fundamental graph problem with widespread applications. However, most existing research on MST focuses on graphs without temporal annotations. This paper investigates the MST problem in the context of temporal graphs. Given an undirected weighted temporal graph, the goal is to compute the MST of the graph within a time window. To overcome the inefficiency of the online algorithm, we propose several index-based query algorithms with provable complexity bounds. Experiments on real-world datasets demonstrate that the proposed methods significantly outperform the baseline online algorithm. Notably, the <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathrm {\Gamma }_b\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="normal">Γ</mi> <mi>b</mi> </msub> </math></EquationSource> </InlineEquation> index, which balances query efficiency and space usage, achieves an average <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(57\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>57</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> speedup over the online algorithm, while incurring only a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(2.82\times \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2.82</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> space overhead on large datasets compared to the original graph. Overall, the proposed indices offer strong performance both theoretically and empirically.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On querying minimum spanning tree in temporal graphs

  • 期刊论文

  • 发表日期：

    2026年7月1日

查看全文
  • Yuanhang Yu,
  • Dong Wen,
  • Lu Qin,
  • Dawei Cheng,
  • Ying Zhang,
  • Wenjie Zhang,
  • Xuemin Lin

摘要

The minimum spanning tree (MST) problem is a fundamental graph problem with widespread applications. However, most existing research on MST focuses on graphs without temporal annotations. This paper investigates the MST problem in the context of temporal graphs. Given an undirected weighted temporal graph, the goal is to compute the MST of the graph within a time window. To overcome the inefficiency of the online algorithm, we propose several index-based query algorithms with provable complexity bounds. Experiments on real-world datasets demonstrate that the proposed methods significantly outperform the baseline online algorithm. Notably, the \(\mathrm {\Gamma }_b\) Γ b index, which balances query efficiency and space usage, achieves an average \(57\times \) 57 × speedup over the online algorithm, while incurring only a \(2.82\times \) 2.82 × space overhead on large datasets compared to the original graph. Overall, the proposed indices offer strong performance both theoretically and empirically.