Bandwidth em grafos
Santa Rita, Vitor Augusto Ferreira / Cerioli, Márcia Rosana
Bandwidth é um problema de otimização combinatória que busca minimizar a maior diferença de rótulos de vértices adjacentes de um grafo G = (V, E), quando rotula-se os vértices de G com números naturais diferentes. Esse problema foi mostrado ser NP-completo, em 1976, e são conhecidas apenas algumas classes de grafos para as quais existe um algoritmo polinomial. Este trabalho apresenta duas demonstrações de NP-completude para o problema, além de...