Bolsa 17/22611-2 - Teoria dos grafos - BV FAPESP
Busca avançada
Ano de início
Entree

Aspectos algorítmicos e estruturais de problemas de cobertura e empacotamento em grafos

Processo: 17/22611-2
Modalidade de apoio:Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
Data de Início da vigência: 01 de outubro de 2018
Data de Término da vigência: 30 de setembro de 2019
Área de conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Flávio Keidi Miyazawa
Beneficiário:Phablo Fernando Soares Moura
Supervisor: Zdenek Dvorak
Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Instituição Anfitriã: Charles University in Prague (CU), República Tcheca  
Vinculado à bolsa:16/21250-3 - Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos, BP.PD
Assunto(s):Teoria dos grafos
Palavra(s)-Chave do Pesquisador:algorithms and complexity | path cover | structural graph theory | subdivision of digraphs | vertex coloring | Teoria dos grafos

Resumo

Este é um projeto de pesquisa para o estágio de Phablo Fernando Soares Moura (FAPESP Proc. 2016/21250-3), pesquisador pós-doutoral sob supervisão do professor Flávio Keidi Miyazawa no Instituto de Computação da Universidade Estadual de Campinas. Esse estágio, a ser realizado na Charles University em Praga, República Tcheca, é planejado para o período de 1 de agosto de 2018 até 31 de julho de 2019 (12 meses). Durante esse período, Phablo será supervisionado pelo professor Zdenek Dvorak. O foco deste projeto de pesquisa é o estudo de problemas de cobertura e empacotamento em grafos e digrafos. Estamos particularmente interessados em estudar o problema de cobertura por caminhos, o problema das Quatro Cores e problemas relativos a conjectura de Mader sobre subdivisão de digrafos. No primeiro problema, queremos cobrir o conjunto de vértices de um grafo usando uma quantidade mínima de caminhos disjuntos nos vértices. No segundo, estudamos a reducibilidade de configurações no contexto do Teorema das Quatro Cores. Finalmente, no contexto da conjectura de Mader, temos como objetivo encontrar condições suficientes para que um digrafo contenha alguma subdivisão de um dado digrafo acíclico.

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

Publicações científicas (6)
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Randomized approximation scheme for Steiner Multi Cycle in the Euclidean plane. THEORETICAL COMPUTER SCIENCE, v. 835, p. 134-155, . (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)
MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. Strong intractability results for generalized convex recoloring problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 252-260, . (16/21250-3, 17/22611-2, 15/11937-9)
ABOULKER, PIERRE; COHEN, NATHANN; HAVET, FREDERIC; LOCHET, WILLIAM; MOURA, PHABLO F. S.; THOMASSE, STEPHAN. Subdivisions in digraphs of large out-degree or large dichromatic number. ELECTRONIC JOURNAL OF COMBINATORICS, v. 26, n. 3, . (15/11930-4, 16/21250-3, 17/22611-2, 13/19179-0)
MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; OTA, MATHEUS J.; WAKABAYASHI, YOSHIKO. Partitioning a graph into balanced connected classes: Formulations, separation and experiments. European Journal of Operational Research, v. 293, n. 3, p. 11-pg., . (16/21250-3, 15/11937-9, 17/22611-2, 16/01860-1)
MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. Strong intractability results for generalized convex recoloring problems. DISCRETE APPLIED MATHEMATICS, v. 281, p. 9-pg., . (16/21250-3, 15/11937-9, 17/22611-2)
LINTZMAYER, CARLA N.; MIYAZAWA, FLAVIO K.; MOURA, PHABLO F. S.; XAVIER, EDUARDO C.. Quasilinear Approximation Scheme for Steiner Multi Cycle in the Euclidean plane. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 13-pg., . (15/11937-9, 17/22611-2, 16/23552-7, 16/01860-1, 16/21250-3)