A heuristic for the convex recoloring problem in graphs

DOI10.1111/ITOR.12896MaRDI QIDQ6071077zbMATH OpenOpenAlexFDO

Authors Cid Carvalho de Souza, Zanoni Dias

Publication date 27 November 2023

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1111/itor.12896

zbMATH Keywords

combinatorial optimizationconvex recoloringGRASP

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites work

• An extended formulation of the convex recoloring problem on a tree
• Column generation approach to the convex recoloring problem on a tree
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Greedy randomized adaptive search procedures
• Improved approximation algorithm for convex recoloring of trees
• On the complexity of solving or approximating convex recoloring problems
• Partial convex recolorings of trees and galled networks
• Statistical comparisons of classifiers over multiple data sets
• The convex recoloring problem: polyhedra, facets and computational experiments

Cited in

(6)

• Improving graph colouring algorithms and heuristics using a novel representation
• Greedy versus recursive greedy: uncorrelated heuristics for the binary paint shop problem
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• A semidefinite programming-based heuristic for graph coloring
• Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks
• An optimal greedy heuristic to color interval graphs

This page was built for publication: A heuristic for the convex recoloring problem in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071077)