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
Vigência (Início): 01 de outubro de 2018
Vigência (Término): 30 de setembro de 2019
Área do 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
Local de pesquisa: 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:
Matéria(s) publicada(s) em Outras Mídias (0 total):
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)
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)
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)
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)

Por favor, reporte erros na lista de publicações científicas utilizando este formulário.