FAPESP Logo

Conjuntos dominantes em grafos planares triangulados

Beneficiário:

Instituição: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas, SP, Brasil
Pesquisador responsável:

Christiane Neme Campos

Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Processo: 08/54219-5
Vigência: 01 de outubro de 2008 - 31 de julho de 2009
Resumo
Este projeto de pesquisa se insere na área de Teoria da Computação, na sub-área de Teoria de Grafos. Aborda dois tópicos importantes da teoria: grafos planares e conjuntos dominantes. A importância dos grafos planares remonta ao "Problema das Quatro Cores", Formulado em 1852, este é o primeiro problema de coloração em grafos conhecido. As tentativas de resolver este problema, o que ocorreu em 1976, foram responsáveis por boa parte do que é hoje conhecido como Teoria de Grafos. Problemas de conjuntos dominantes começaram a ser estudados no início da década de 60 e têm despertado o interesse de muitos pesquisadores, tanto por suas características teóricas, como também por sua aplicabilidade. Exemplos de aplicações incluem o problema de como distribuir torres de energia, ou telefonia celular, de maneira a garantir a cobertura de uma certa área geográfica. Iniciaremos este projeto de iniciação científica com o estudo de aspectos básico da teoria de grafos, em grafos planares. Posteriormente, serão estudados os problemas de conjuntos dominantes e algumas de suas variações. O projeto se encerrará com o estudo de uma conjetura proposta por R. Tarjan, renomado pesquisador da área de Teoria dos Grafos, a respeito de conjuntos dominantes em grafos planares triangulados. (AU)
CDi/FAPESP - Centro de Documentação e Informação da Fundação de Amparo à Pesquisa do Estado de São Paulo

R. Pio XI, 1500 - Alto da Lapa - CEP 05468-901 - São Paulo/SP - Brasil
cdi@fapesp.br - Converse com a FAPESP