Busca avançada
Ano de início
Entree

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)

Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)