A data structure for spanning tree optimization problems (2019)
- Authors:
- Autor USP: BARBOSA, MARCO AURÉLIO LOPES - ICMC
- Unidade: ICMC
- Sigla do Departamento: SSC
- DOI: 10.11606/T.55.2019.tde-29082019-141240
- Subjects: COMPUTAÇÃO EVOLUTIVA; DADOS CINÉTICOS; OTIMIZAÇÃO GLOBAL
- Keywords: Algoritmos de busca local; Algoritmos evolutivos; Árvores geradoras; Dynamic tree data structures; Estrutura de dados de árvores dinâmicas; Evolutionary algorithms; Local search algorithms; Spanning trees
- Language: Inglês
- Abstract: Os problemas de otimização de árvores geradoras estão relacionados a muitas aplicações práticas. Vários desses problemas são NP-difícies, o que limita a utilidade de métodos exatos e pode exigir abordagens alternativas, como metaheurísticas. Um questão relevante para muitas metaheurísticas é a estrutura de dados usada para representar e manipular as soluções. Uma estrutura de dados com operações eficientes pode aumentar a utilidade de um método, permitindo que instâncias maiores sejam resolvidas em um período de tempo razoável. Propomos a estrutura de dados 2LETT e a usamos para representar árvores geradoras em duas metaheurísticas: algoritmos evolutivos baseados em mutações e algoritmos de busca local. A operação principal da 2LETT é a troca de uma aresta na árvore representada por outra aresta. Esta operação tem tempo de O(√n), onde n é o número de vértices na árvore. Conduzimos avaliações qualitativas e quantitativas para 2LETT e outras estruturas na literatura. Para a principal operação de troca de arestas em algoritmos evolutivos, os experimentos computacionais mostram que a 2LETT possui o melhor desempenho para árvores com mais de 10.000 vértices. Para algoritmos de busca local, o 2LETT é a melhor opção para lidar com árvores grandes com grandes diâmetros.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2019
- Data da defesa: 17.06.2019
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
BARBOSA, Marco Aurélio Lopes. A data structure for spanning tree optimization problems. 2019. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2019. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/. Acesso em: 09 maio 2026. -
APA
Barbosa, M. A. L. (2019). A data structure for spanning tree optimization problems (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/ -
NLM
Barbosa MAL. A data structure for spanning tree optimization problems [Internet]. 2019 ;[citado 2026 maio 09 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/ -
Vancouver
Barbosa MAL. A data structure for spanning tree optimization problems [Internet]. 2019 ;[citado 2026 maio 09 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-29082019-141240/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
