Vinicius Fernandes dos Santos  —   Graph Classes

Vinicius Fernandes dos Santos  —   Classes de Grafos

Main page

Página principal

Disciplina: Classes de Grafos

Esta é uma disciplina de foco teórico que busca dar uma visão geral da estrutura de grafos que aparecem em determinados contextos. Uma motivação para o estudo de classes de grafos é o fato de que diversos problemas NP-difíceis podem ser resolvidos em tempo polinomial para determinadas classes. Assim, utilizando-se informação sobre os grafos do contexto onde pretendemos resolver o problema, pode-se encontrar soluções mais eficiente que no caso geral.

Para cursar essa disciplina, é necessário conhecimento de conceitos de Matemática Discreta, Algoritmos e Complexidade de Algoritmos. Não é necessário um conhecimento específico de Algoritmos em Grafos.


Professor:

• Vinicius dos Santos

Programa:

• Grafos de Interseção
• Grafos de Intervalo
• Grafos Cordais
• Grafos Linha
• Grafos Disco Unitário
• Grafos de Comparabilidade
• Cografos
• Grafos Aleatórios

Bibliografia:

• A. Bondy, U.S.R. Murty, Graph Theory, Springer-Verlag London, 2008.
• A. Brandstädt, V. B. Le e J. P. Spinrad, Graph Classes: a Survey. SIAM, 1999.
• M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004.
• T. A. McKee e F. R. McMorris, Topics in Intersection Graph Theory, SIAM, 1999.

Bibliografia complementar:

• J. R. S. Blair, B. Peyton. An introduction to chordal graphs and clique trees. Technical Report, Oak Ridge National Laboratory, 1993.

Listas de Exercícios:

• Lista 1.
• Lista 2.

Trabalho:

• Lista de classes de grafos.