COS842 - Tópicos Especiais em Algoritmos e Grafos
2017/1 - Professores Daniel Posner / Márcia R. Cerioli
Objetivos:
Reconhecer propriedades estruturais de classes de grafos, em especial dos grafos com poucos P4's e fracamente cordais (e suas subclasses).
Utilizar tais estruturas para, de forma eficiente, reconhecer grafos nessas classes e solucionar problemas de otimização tais como coloração de vértices, clique máxima, e outros de interesse dos alunos.
Ementa:
- Grafos com poucos P4's
- Cografo (sem P4's)
- Threshold
- P4-esparço
- P4-tidy
- grafo (q,q-4)
- Fracamente cordais
- cordal
- split
- bipartido cordal
- fortemente cordal
Bibliografia:
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.
- ISGCI - Intersection
System on Graph Class Inclusions
J. P. Spinrad
Efficient Graph Representation
AMS, 2003.
Pré-requisitos:
Conhecimentos básicos de teoria de grafos, usualmente vistos em um curso introdutório.
(árvores, planaridade, grafos bipartidos, ...)
Veja aqui uma lista de exercícios para teste de domínimo de pré-requisito.
Página criada em 13 jun 00 e atualizada em 18 fev, 7 mar, 17 mar 17 por
Márcia R. Cerioli