Uma análise experimental sobre a t-admissibilidade em grafos

A t-admissibilidade consiste em decidir se um grafo G admite uma árvore geradora T na qual a máxima distância entre dois vértices adjacentes em G é no máximo t. O menor t para o qual G seja t-admissível é σT(G), chamado de índice de extensão de G. Sob a perspectiva do problema de otimização, visamos determinar uma árvore geradora que minimize a máxima distância entre dois vértices adjacentes em G. Determinar se σG ≤ t para t ≥ 4 é um problema NP-completo. Desenvolvemos e implementamos um algoritmo de força bruta sequencial, um de computação paralela e duas heurísticas gulosas. Comparamos essas implementações em grafos aleatórios Erdös-Rényi, e além disso, determinamos uma classe onde uma das heurísticas determina o índice de extensão corretamente.