COS842 - Tópicos Especiais em Algoritmos e Grafos
2017/1 - Professores Daniel Posner / Márcia R. Cerioli
Monografia/seminário:
Apresentar um problema de otimização e qual é o status de sua complexidade nas classes de grafos estudadas na disciplina.
Espera-se que as propriedades estruturais dos grafos na classes estudadas sejam de relevância para a resolução do problema escolhido. Isto é, que os teoremas estudados na disciplina sejam utilizados nestas aplicações.
Classes:
- 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
Roteiro:
(A) Definição do problema: definição, exemplos, comentários
(B) breve motivação, histórico revisão de sua complexidade em classes de grafos conhecidas (planares, bipartidos,...)
(C) Sua complexidade em todas as classes de grafos da disciplina.
(D) Citar as classes de grafos que serão abordadas em detalhes e quais são os resultados.
(E) Desenvolvimento dos resultados citados em (D)
A monografia/slides/seminário deve incluir a prova detalhada de pelo menos dois teoremas.
(F) Referências.
Prazo: primeira versão (de uma página com ao menos (A), (D) e (F)): 18 de abril.
Segunda versão (completa): no dia do seminário.
Página criada em 13 abr 17 e atualizada em 22 abr por
Márcia R. Cerioli