| Processo: | 15/11930-4 |
| Modalidade de apoio: | Bolsas no Exterior - Estágio de Pesquisa - Doutorado |
| Data de Início da vigência: | 01 de setembro de 2015 |
| Data de Término da vigência: | 31 de agosto de 2016 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Pesquisador responsável: | Yoshiko Wakabayashi |
| Beneficiário: | Phablo Fernando Soares Moura |
| Supervisor: | Stephan Thomasse |
| Instituição Sede: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil |
| Instituição Anfitriã: | École Normale Supérieure, Lyon (ENS), França |
| Vinculado à bolsa: | 13/19179-0 - Problemas de otimização sobre partição em grafos, BP.DR |
| Assunto(s): | Grafos Teoria dos grafos |
| Palavra(s)-Chave do Pesquisador: | coloração de vértices | orientação de arestas | particionamento de grafos | particionamento em caminhos | Teoria dos Grafos e Otimização |
Resumo O foco desta proposta de pesquisa é o estudo de problemas de particionamento em grafos. Estamos particularmente interessados nos problemas de orientação própria, cobertura por caminhos e recoloração convexa. No primeiro problema, devemos orientar todas as arestas de um grafo de tal forma que os graus de entrada dos vértices nessa orientação induzam um particionamento do conjunto de vértices em uma quantidade mínima de conjuntos estáveis. No segundo problema, estamos interessados em encontrar uma partição do conjunto de vértices de um grafo em um número mínimo de caminhos. Finalmente, no problema de recoloração convexa, temos que particionar o conjunto de vértices do grafo de tal forma que cada elemento da partição induza um subgrafo conexo do grafo de entrada. (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) | |