Busca avançada
Ano de início
Entree

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

Processo: 13/19179-0
Linha de fomento:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de dezembro de 2013
Vigência (Término): 31 de março de 2017
Área do 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

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.

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)
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. Citações Web of Science: 0.
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, NOV 2017. Citações Web of Science: 1.
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, AUG 2016. Citações Web of Science: 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, MAR 2016. Citações Web of Science: 2.
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 São Paulo.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.