Back to Search
Start Over
Building Minimum Spanning Trees under Maximum Edge Length Constraint.
- Source :
- Information Technology & Management Science; 2023, Vol. 26, p17-26, 10p
- Publication Year :
- 2023
-
Abstract
- Given an initial set of planar nodes, the problem is to build a minimum spanning tree connecting the maximum possible number of nodes by not exceeding the maximum edge length. To obtain a set of edges, a Delaunay triangulation is performed over the initial set of nodes. Distances between every pair of the nodes in respective edges are calculated used as graph weights. The edges whose length exceeds the maximum edge length are removed. A minimum spanning tree is built over every disconnected graph. The minimum spanning trees covering a maximum of nodes are selected, among which the tree whose length is minimal is the solution. It is 1.17 % shorter on average for 10 to 80 nodes compared to a nonselected tree. [ABSTRACT FROM AUTHOR]
- Subjects :
- SPANNING trees
TRIANGULATION
EDGES (Geometry)
GRAPH theory
TREE graphs
Subjects
Details
- Language :
- English
- ISSN :
- 22559086
- Volume :
- 26
- Database :
- Complementary Index
- Journal :
- Information Technology & Management Science
- Publication Type :
- Academic Journal
- Accession number :
- 173918230
- Full Text :
- https://doi.org/10.7250/itms-2023-0003