Aurora Morgana | Università degli Studi di Roma La Sapienza - Itália

• Processo: 04/10301-9
• Modalidade de apoio: Auxílio à Pesquisa - Pesquisador Visitante - Internacional
• Data de Início da vigência: 15 de novembro de 2004
• Data de Término da vigência: 14 de dezembro de 2004
• Área do 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: Celia Picinin de Mello
• Pesquisador visitante: Aurora Morgana
• Instituição do Pesquisador Visitante: Università degli Studi di Roma La Sapienza, Itália
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Teoria dos grafos Intercâmbio de pesquisadores Colaboração científica
• Palavra(s)-Chave do Pesquisador: Cografo | Decomposicao Modular | Grafo P4 Reduzido | Operador Clique

Resumo

Serão considerados dois problemas: operador clique e problemas sanduíche em grafos. No primeiro, o objetivo é caracterizar a classe dos grafos clique dos cografos. Sabemos apenas quais são os cografos que possuem grafo clique que é, também, um cografo. No segundo, o objetivo ô determinar se existe um grafo sanduíche satisfazendo a propriedade de "ser grafo P4-reduzido". Sabemos que existe algoritmo polinomial que decide a existência de cografo sanduíche e que é NP-completo resolver o problema sanduíche quando a propriedade é "ser grafo de permutação". A classe dos grafos P4-reduzidos é uma superclasse dos cografos e uma subclasse dos grafos permutação. Objetivo geral: Dar continuidade ao acordo de cooperação estabelecido entre a UNICAMP e a Università di Roma "La Sapienza" (proc. 34P-10647/03 e termo aditivo 01 (34P-10649/03). (AU)