Bolsa 13/19179-0 - - BV FAPESP
Busca avançada
Ano de início
Entree

Problemas de otimização sobre partição em grafos

Processo: 13/19179-0
Modalidade de apoio:Bolsas no Brasil - Doutorado
Data de Início da vigência: 01 de dezembro de 2013
Data de Término da vigência: 31 de março de 2017
Á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
Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Bolsa(s) vinculada(s):15/11930-4 - Problemas de particionamento em grafos, BE.EP.DR
Palavra(s)-Chave do Pesquisador:coloração (convexa) | complexidade e algoritmos | estudo poliédrico | partição em grafos | Otimização em grafos

Resumo

Este é um projeto de pesquisa para doutorado de Phablo Fernando Soares Moura, a ser desenvolvido sob a orientação de Y. Wakabayashi, no Instituto de Matemática e Estatística da USP. Ele se insere na área de otimização combinatória, e tem como foco problemas de partição em grafos com certas restrições. Um dos problemas que serão investigados neste projeto é o problema da recoloração convexa de grafos. Em linhas gerais, neste problema a entrada é um grafo cujos vértices estão coloridos (arbitrariamente), e o objetivo é trocar a cor de um número mínimo de vértices de modo a obter uma coloração tal que, para cada cor, o grafo induzido pelos vértices com essa cor é conexo. Basicamente, a recoloração objetiva definir uma partição do conjunto dos vértices do grafo, tal que cada classe da partição induz um subgrafo conexo de uma das possíveis cores.Este problema tem suas raízes no estudo de árvores filogenéticas, mas estende-se facilmente para versões mais gerais e em grafos arbitrários, tendo sido objeto de estudo sob diversas abordagens. Trata-se de um problema NP-difícil já no caso especial de caminhos. Propomos investigar versões mais gerais desse problema em grafos arbitrários, tendo como foco o estudo de formulações distintas, a relação entre tais formulações e aspectos algorítmicos.

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 (4)
(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)
COELHO, RAFAEL S.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The k-hop connected dominating set problem: approximation and hardness. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 34, n. 4, p. 1060-1083, . (13/03447-6, 15/11930-4, 13/19179-0)
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)
CAMPELO, MANOEL; MOURA, PHABLO F. S.; SANTOS, MARCIO C.. Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope. DISCRETE OPTIMIZATION, v. 21, p. 131-156, . (13/03447-6, 15/11930-4, 13/19179-0)
CAMPELO, MANOEL; FREIRE, ALEXANDRE S.; LIMA, KARLA R.; MOURA, PHABLO F. S.; WAKABAYASHI, YOSHIKO. The convex recoloring problem: polyhedra, facets and computational experiments. MATHEMATICAL PROGRAMMING, v. 156, n. 1-2, p. 303-330, . (13/03447-6, 13/19179-0, 12/17585-9)
Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
MOURA, Phablo Fernando Soares. Colorações de grafos e subdivisões de digrafos. 2017. Tese de Doutorado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.

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