.png){kind=icon}
.png){kind=icon}
Return
Genetic algorithms to balanced tree structures in graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.swevo.2016.06.005.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given an edge-weighted graph G = (V, E) with vertex set V and edge set E, we study in this paper the following related balanced tree structure problems in G. The first problem, called Constrained Minimum Spanning Tree Problem (CMST), asks for a rooted tree Tin G that minimizes the total weight of T such that the distance between the root and any vertex v in T is at most a given constant C times the shortest distance between the two vertices in G. The Constrained Shortest Path Tree Problem (CSPT) requires a rooted tree Tin G that minimizes the maximum distance between the root and all vertices in V such that the total weight of T is at most a given constant C times the minimum tree weight in G. The third problem, called Minimum Maximum Stretch Spanning Tree (MMST), looks for a tree Tin G that minimize the maximum distance between all pairs of vertices in V. It is easy to conclude from the literatures that the above problems are NP-hard. We present efficient genetic algorithms that return (as shown by our experimental results) high quality solutions for these problems. (C) 2016 Elsevier B.V. All rights reserved.
Keywords:
Minimum Spanning Tree
Shortest Path Tree
Tree Spanner
Balanced Spanning Tree
Minimum Maximum Stretch Spanning Tree
Genetic Algorithms
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
8.5
Papers:
2.2K
Citations:
1.0W