Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

The convex recoloring problem: polyhedra, facets and computational experiments

Texto completo
Autor(es):
Campelo, Manoel [1] ; Freire, Alexandre S. [2] ; Lima, Karla R. [3] ; Moura, Phablo F. S. [4] ; Wakabayashi, Yoshiko [4]
Número total de Autores: 5
Afiliação do(s) autor(es):
[1] Univ Fed Ceara, Dept Estat & Matemat Aplicada, Fortaleza, Ceara - Brazil
[2] Univ Estadual Campinas, Inst Computacao, Campinas, SP - Brazil
[3] Univ Sao Paulo, Escola Artes Ciencias & Humanidades, Sao Paulo - Brazil
[4] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Número total de Afiliações: 4
Tipo de documento: Artigo Científico
Fonte: MATHEMATICAL PROGRAMMING; v. 156, n. 1-2, p. 303-330, MAR 2016.
Citações Web of Science: 3
Resumo

A coloring of the vertices of a graph is convex if the vertices receiving a common color induce a connected subgraph of . We address the convex recoloring problem: given a graph and a coloring of its vertices, recolor a minimum number of vertices of , so that the resulting coloring is convex. This problem is known to be -hard even when is a path. We show an integer programming formulation for arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We consider instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to vertices in 2 h, comparing favorably to other approaches that have been proposed in the literature. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 12/17585-9 - Técnicas de modelagem para resolução de problemas de otimização combinatória
Beneficiário:Alexandre da Silva Freire
Linha de fomento: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 13/19179-0 - Problemas de otimização sobre partição em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Brasil - Doutorado