Bandwidth em Grafos
Autores
|
4863 |
Vitor Augusto Ferreira Santa Rita
|
2171,410
|
|
4864 |
2171,410
|
Informações:
Publicações do PESC
Título
Bandwidth em Grafos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
6/9/2010
Resumo
Bandwidth é um problema de otimização combinatória que busca minimizar a maior diferença dos rótulos dos 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. Esta dissertação apresenta duas demonstrações de NP-completude para o problema, além de apresentar os principais algoritmos polinomiais existentes bem como dois algoritmos exponenciais exatos para a classe geral de grafos.
Abstract
Bandwidth is a combinatorial optimization problem that consists in minimizing the greatest difference among labels of adjacent vertices in a graph G = (V,E), when those vertices are labeled with distinct natural numbers. This problem was shown to be NP-complete, in 1976, and only a few subclasses are known to have a polinomial time algorithm. This dissertation shows two NP-complete demonstrations of the problem, besides presenting the principals polinomial time algorithms of classes of graphs together with two exact exponential time algorithms to the general class of graphs.
Arquivo