Genetic algorithms to balanced tree structures in graphs

详细信息    查看全文

• 作者：Riham Moharam ^{riham.moharam@science.suez.edu.eg} ; Ehab Morsy ; ^{ehabmorsy@science.suez.edu.eg}
• 关键词：Minimum Spanning Tree ; Shortest Path Tree ; Tree Spanner ; Balanced Spanning Tree ; Minimum Maximum Stretch Spanning Tree ; Genetic Algorithms
• 刊名：Swarm and Evolutionary Computation
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：32
• 期：Complete
• 页码：132-139
• 全文大小：1116 K
• 卷排序：32

文摘

Given an edge-weighted graph G=(V,E)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 T in 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 T in 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 T in 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.