.png){kind=icon}
返回
Dynamically Reconstructing Minimum Spanning Trees After Swapping Pairwise Vertices
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2019.2894829.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The minimum spanning tree (MST) problem is a fundamental problem in computer science and operations research, which has many real-life network design applications. Given a graph G with n vertices and m edges, starting from an MST (denoted by T) covering a subgraph of G, it is usually needed to reconstruct a new MST after swapping two vertices v is an element of T and v' is not an element of T. For this purpose, the most popular choice is to reconstruct an MST from scratch, for which the current fastest algorithm (Kruskal's algorithm based on Fibonacci heap) requires a time complexity of O(m + n . log n), implying that a high time complexity of O(n(2)) . O(m + n . log n) is needed to evaluate all the O(n(2)) possible swapping-based moves. In order to evaluate these moves more efficiently, we integrate a series of dynamic techniques to develop a fast dynamic swap-vertex move operator, which significantly reduces the overall time complexity from O(n(2)) . O(m + n . log n) to O(n) . O(m . log n). We also strictly prove the correctness of the introduced method. Finally, we choose three well-studied Steiner/spanning tree problems as our test bed and carry out extensive experiments on 140 representative instances to show the effectiveness and efficiency of the proposed method. More importantly, as a general-purpose method, the dynamic swap-vertex move operator could be easily adapted to many other tree-related problems.
Keyword:
Dynamic data structure
Steiner/spanning tree problems
swap-vertex move operator
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.6
论文数:
9.8W
被引数:
29.4W
机构
引用论文
A two-level solution approach for solving the generalized minimum spanning tree problem求解广义最小生成树问题的两级解法
PREAI
分享收藏分享收藏Experimental study of the relationship between the base impedance and its time derivative in impedance plethysmography阻抗体积描记法中基本阻抗与其时间导数关系的实验研究
PREAI
分享收藏The structure of gentioflavine, a new alkaloid of some Gentiana species龙胆黄素的结构，一种某些Gentiana物种的新型生物碱.png)
Tetrahedron
TetrahedronIF0
PREAI
分享收藏分享收藏Distributed Sub-Tree-Based Optical Multicasting Scheme in Elastic Optical Data Center NetworksIEEE ACCESSOAAI
IEEE ACCESSIF3.6
OAAI分享收藏
查看更多内容