.png){kind=icon}
返回
Data Structures for Direct Spanning Tree Representations in Mutation-Based Evolutionary Algorithms
.png){kind=icon}
PRE
AI
DOI：10.1109/TEVC.2019.2928991.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Optimization methods for spanning tree problems may require efficient data structures. The node-depth-degree representation (NDDR) has achieved relevant results for direct spanning tree representation together with evolutionary algorithms (EAs). Its two mutation operators have average time O(root n), where n is the number of vertices of the graph, while similar operators implemented by predecessor arrays, a typical tree data structure, have time O(n). Dynamic trees are also relevant when investigating tree representations since they have low time complexity, but there is no proper extension of them for EAs. Using aspects of both a dynamic tree and NDDR, namely, Euler tours and structural sharing, we propose a data structure called 2LETT, whose mutation operators have time O(root n) in the worst case. Experiments with the mutation operators using 2LETT, predecessor arrays, and NDDR are carried out for graphs with up to 300 000 vertices. For a mutation operator that exchanges any two valid edges, predecessor arrays present the best performance for random trees with fewer than 10 000 vertices; while 2LETT has the best performance for trees with more than 10 000 vertices. Especially, noteworthy is the fact that 2LETT is the only structure whose running time is independent of tree diameter.
Keyword:
Dynamic tree data structures
evolutionary algorithms (EAs)
tree representations
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
12
论文数:
1.8K
被引数:
2.4W
机构
引用论文
Bioinformatics analysis of pectin methylesterase inhibitor MePMEI1 from Manihot esculenta Crantz.png)
IF0
PREAI
分享收藏
查看更多内容