Busca avançada
Ano de início
Entree

Aspectos algorítmicos e estruturais de problemas de Cobertura e Empacotamento em grafos

Processo: 16/21250-3
Modalidade de apoio:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de abril de 2017
Vigência (Término): 13 de outubro de 2019
Área do 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:
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.