Data Structures for Direct Spanning Tree Representations in Mutation-based Evolutionary Algorithms
| Autor: | Marco Aurelio Lopes Barbosa, Letícia Rodrigues Bueno, Alexandre C. B. Delbem |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Spanning tree
ALGORITMOS E ESTRUTURAS DE DADOS Evolutionary algorithm 02 engineering and technology Data structure Evolutionary computation Theoretical Computer Science Running time Combinatorics Tree (data structure) symbols.namesake Computational Theory and Mathematics 0202 electrical engineering electronic engineering information engineering Euler's formula symbols 020201 artificial intelligence & image processing Time complexity Software |
| Zdroj: | Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual) Universidade de São Paulo (USP) instacron:USP |
| ISSN: | 1941-0026 1089-778X |
| DOI: | 10.1109/tevc.2019.2928991 |
| Popis: | 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(\sqrt {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(\sqrt {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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|