Conjuntos dominantes em grafos planares triangulados

• Processo: 08/54219-5
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2008
• Data de Término da vigência: 31 de julho de 2009
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Christiane Neme Campos
• Beneficiário: Izumi Oniki Chiquito
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Conjuntos Dominantes | Grafos Planares | Teoria De Grafos

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)