Autores

6261
2845,413,414
6262
2845,413,414
6263
2845,413,414

Informações:

Publicações do PESC

Título
Alguns Resultados em Espessura de Grafos
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
15/4/2005
Resumo

Este trabalho descreve dois conceitos importantes relativos à espessura de um grafo. A espessura de um grafo G = (V, E) é o número mínimo de subgrafos planares necessários para decompor o grafo G. O primeiro conceito mostra uma fórmula para a espessura de um grafo completo K7, em função do número n de vértices, exibindo os passos da decomposição deste grafo. O segundo conceito apresenta uma prova da NP-completude do problema de decisão de espessura, mesmo considerando k = 2, onde k é o tamanho da espessura de um grafo G.

Abstract
Arquivo
Topo