.png){kind=icon}
.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Graph theory
Minimum spanning tree
Bounded diameter minimum spanning tree
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W