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.

Publicações científicas

(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, OCT 2 2020. (16/23552-7, 16/21250-3, 17/22611-2, 15/11937-9, 16/01860-1)

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, JUL 19 2019. (15/11930-4, 16/21250-3, 17/22611-2, 13/19179-0)

MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. Strong intractability results for generalized convex recoloring problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 252-260, JUL 15 2020. (16/21250-3, 17/22611-2, 15/11937-9)