A heuristic for the convex recoloring problem in graphs

Ana Paula S. Dantas; Cid C. de Souza; Zanoni Dias

doi:10.1111/itor.12896

journal article Nov 06, 2020

A heuristic for the convex recoloring problem in graphs

Ana Paula S. Dantas

Cid C. de Souza

Zanoni Dias

International Transactions in Operational Research Vol. 29 No. 3 pp. 1454-1478 · Wiley

View at Publisher Save 10.1111/itor.12896

Abstract

AbstractWe consider a coloring as a function that assigns a color to a vertex, regardless of the color of its neighbors. In this sense, a coloring is said to be convex if every set of all same colored vertices induces a connected subgraph. The Convex Recoloring Problem finds the minimum number of recolored vertices needed to turn a coloring convex. This problem is most commonly studied considering trees due to its origins in Computational Biology, but in this paper, we focus on general graphs. We propose a heuristic based on the Greedy Randomized Adaptive Search Procedure to solve the problem. We present computational experiments for our heuristic and compare it to an Integer Linear Programming (ILP) model from the literature. In these experiments, our heuristic recolored at most one vertex more than the ILP model, and it was also able to give better solutions when the ILP model was unable to find the optimal solution within the time limit. We also introduce a set of benchmark instances for the problem.

Topics

No keywords indexed for this article. Browse by subject →

References

19

[1]

10.1016/j.tig.2013.05.007

[2]

10.1007/s00224-007-9069-7

[3]

Bondy J.A. (2011)

[4]

10.1007/s10107-015-0880-7

[5]

Campêlo M.B. Huiban C.G. Sampaio R.M. Wakabayashi Y. 2013. On the complexity of solving or approximating convex recoloring problems. Proceedings of the 19th International Computing and Combinatorics Conference (COCOON'2013) Springer Berlin Heidelberg pp.614–625. 10.1007/978-3-642-38768-5_54

[6]

Chopra S. Erdem E. Kim E. Shim S. 2016. Column generation approach to the convex recoloring problem on a tree. Proceedings of the 16th Modeling and Optimization: Theory and Applications Conference (MOPTA'2016) Springer International Publishing Cham Switzerland pp.39–53. 10.1007/978-3-319-66616-7_3

[7]

10.1007/s10107-016-1094-3

[8]

Chor B. Fellows M. Ragan M.A. Razgon I. Rosamond F. Snir S. 2007. Connected coloring completion for general graphs: algorithms and complexity. Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON'2007) Springer Berlin Heidelberg pp.75–85. 10.1007/978-3-540-73545-8_10

[9]

Demšar J. "Statistical comparisons of classifiers over multiple data sets" Journal of Machine Learning Research (2006)

[10]

10.1016/j.entcs.2011.06.003

[11]

Greedy Randomized Adaptive Search Procedures

Thomas A. Feo, Mauricio G. C. Resende

Journal of Global Optimization 10.1007/bf01096763

[12]

10.1016/j.ympev.2016.10.018

[13]

10.1007/3-540-60044-2_38

[14]

10.1016/j.orp.2016.09.002

[15]

10.1016/j.jcss.2007.10.003

[16]

10.1145/2000807.2000810

[17]

Moura P.F.S. 2017. Graph colorings and digraph subdivisions. PhD thesis Instituto de Matemática e Estatística Universidade de São Paulo. 10.5753/ctd.2018.3655

[18]

10.1007/0-387-25383-1_2

[19]

10.1007/978-1-4419-1665-5_10

Metrics

1

Citations

19

References

Details

Published: Nov 06, 2020
Vol/Issue: 29(3)
Pages: 1454-1478
License: View

Authors

A

Ana Paula S. Dantas

Institute of Computing University of Campinas (Unicamp) Av. Albert Einstein Campinas São Paulo 1251 Brazil

C

Cid C. de Souza

Institute of Computing University of Campinas (Unicamp) Av. Albert Einstein Campinas São Paulo 1251 Brazil

Z

Zanoni Dias

Institute of Computing University of Campinas (Unicamp) Av. Albert Einstein Campinas São Paulo 1251 Brazil

Funding

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Award: 001

Conselho Nacional de Desenvolvimento Cientifico e Tecnologico Award: 304380/2018‐0

Fundação de Amparo a Pesquisa do Estado de São Paulo Award: 2015/11937‐9

Cite This Article

Ana Paula S. Dantas, Cid C. de Souza, Zanoni Dias (2020). A heuristic for the convex recoloring problem in graphs. International Transactions in Operational Research, 29(3), 1454-1478. https://doi.org/10.1111/itor.12896

A heuristic for the convex recoloring problem in graphs

You May Also Like