.png){kind=icon}
.png){kind=icon}
Return
On querying minimum spanning tree in temporal graphs
.png){kind=icon}
PRE
AI
DOI：10.1007/s00778-026-00989-1.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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$$ index, which balances query efficiency and space usage, achieves an average $$57\times $$ speedup over the online algorithm, while incurring only a $$2.82\times $$ space overhead on large datasets compared to the original graph. Overall, the proposed indices offer strong performance both theoretically and empirically.
Keywords:
Temporal Graphs
Minimum Spanning Tree
Index-based retrieval
Index maintenance
Journal
T
IF:
0
Papers:
36
Citations:
0
View more organizations