| Processo: | 16/21250-3 |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Data de Início da vigência: | 01 de abril de 2017 |
| Data de Término da vigência: | 13 de outubro de 2019 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Acordo de Cooperação: | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) |
| Pesquisador responsável: | Flávio Keidi Miyazawa |
| Beneficiário: | Phablo Fernando Soares Moura |
| Instituição Sede: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil |
| Bolsa(s) vinculada(s): | 17/22611-2 - Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos, BE.EP.PD |
| Assunto(s): | Algoritmos de aproximação Teoria dos grafos |
| Palavra(s)-Chave do Pesquisador: | Algoritmos de Aproximação | Cobertura | Empacotamento | teoria dos grafos | Otimização combinatória e teoria dos grafos |
Resumo Este é o projeto de pesquisa de pós-doutorado de Phablo F. S. Moura, a ser desenvolvido sob a supervisão do professor Flávio K. Miyazawa, no Instituto de Computação da Universidade Estadual de Campinas (UNICAMP). O projeto se insere nas áreas de algoritmos e teoria dos grafos, e tem como foco o estudo de problemas de cobertura e empacotamento em grafos. Neste projeto, pretendemos investigar os seguintes problemas.O primeiro consiste em particionar (ou seja, cobrir e empacotar) o conjunto de vértices de um grafo de tal forma que cada parte induza um subgrafo conexo e, além disso, as partes sejam balanceadas, ou seja, o peso da parte mais leve é maximizado.No segundo problema, estamos interessados em cobrir o conjunto de vértices de um grafo usando o menor número possível de caminhos. Esse é uma generalização do clássico problema do caminho Hamiltoniano.O terceiro problema apresentado neste projeto é relacionado à uma conjectura que trata de encontrar condições suficientes para que todo grafo direcionado contenha, como subgrafo, alguma subdivisão de um dado grafo direcionado. (AU) | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |