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 apresentar os principais algoritmos polinomiais existentes bem como dois algoritmos exponenciais exatos para a classe geral de grafos.
Lieferbar
ISBN | 9783841720078 |
---|---|
Sprache | por |
Cover | Kartonierter Einband (Kt) |
Verlag | Novas Edições Acadêmicas |
Jahr | 20190902 |
Dieser Artikel hat noch keine Bewertungen.