ANÁLISE DA UTILIZAÇÃO DE ÁRVORES DINÂMICAS PARA A OTIMIZAÇÃO DO ALGORITMO DE DINIC EM PROBLEMAS DE FLUXO MÁXIMO EM GRAFOS

Vol 53, 2021 - 139542
Trabalho completo (oral)
Favorite this paper
How to cite this paper?
Abstract

Uma das principais aplicações das árvores dinâmicas é a otimização do algoritmo de Dinic, utilizado para resolver o problema do fluxo máximo em grafos. Neste artigo é apresentada uma análise da utilização destas estruturas e uma de suas soluções, denominada Link-cut tree, para a otimização deste algoritmo. Foram realizados testes para comparar o algoritmo original de Dinic com a versão otimizada. Os resultados mostram que o algoritmo mais rápido pode variar dependendo do grafo de entrada e a escolha deve ser baseada nas características dos grafos dados.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal de Itajubá
  • 2 Universidade Federal do ABC
Track
  • 19 - TAG - Theory and Algorithms in Graphs
Keywords
Link-cut tree
Árvores Splay
Problema do fluxo máximo