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)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

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.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal de Itajubá
  • 2 Universidade Federal do ABC
Eixo Temático
  • 19 - TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Link-cut tree
Árvores Splay
Problema do fluxo máximo