.png){kind=icon}
返回
Finding bounded diameter minimum spanning tree in general graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2022.105822.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Given a connected, weighted, undirected graph G = (V, E) and a constant D >= 2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight with diameter no more than D. A new algorithm addresses graphs with non-negative weights and has proven performance ratio of O((1 - D/d(min)(vertical bar V vertical bar-1)omega(+)/omega(-) + 1), omega(+) (resp. omega(-)) denotes the maximum (resp. minimum) edge weight in the graph, and d(min )is the hop diameter of G. The running time of the algorithm is O (vertical bar V vertical bar log D) after minimum spanning tree of G is computed. The performance of the algorithm has been evaluated empirically as well.
Keyword:
Graph theory
Minimum spanning tree
Bounded diameter minimum spanning tree
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容