Cliques maximais em cografos.

• Processo: 03/11922-4
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de fevereiro de 2004
• Data de Término da vigência: 31 de dezembro de 2004
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Celia Picinin de Mello
• Beneficiário: Renato Capello
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos | Cliques Maximais | Cografos | Grato Clique | Gratos Multipartidos Complexos

Resumo

Este projeto considera as cliques maximais de um grafo, em particular, as cliques maximais dos cografos. (Um grafo é um cografo se não contiver P4 como subgrafo induzido.) Desejamos determinar como essas cliques se relacionam. Um grafo que exibe essas relações é conhecido como grafo clique. Estudaremos, portanto, os grafos clique dos cografos. Para atingir este objetivo, estudaremos a classe dos cografos, seu reconhecimento, suas caracterizações e algoritmos relacionados ao problema de determinar o número de cliques maximais dos cografos. Em relação aos grafos clique, estudaremos a classe dos grafos clique dos grafos indiferença, dos cordais, e de vários subconjuntos dos cografos que se encontram na literatura. É bom ressaltar que a classe dos grafos clique dos cografos ainda não está totalmente determinada. (AU)