Recombinative approaches for the maximum happy vertices problem

Thiruvady, Dhananjay and Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X 2022. Recombinative approaches for the maximum happy vertices problem. Swarm and Evolutionary Computation 75 , 101188. 10.1016/j.swevo.2022.101188

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview

Abstract

The maximum happy vertices problem involves taking a simple graph in which several vertices are precoloured. The aim is to colour the remaining vertices to maximise the number happy vertices, where a vertex is considered happy if and only if all of its neighbours are assigned the same colour as the vertex itself. Previous studies for this problem have investigated integer programming, tabu search and the construct, solve, merge & adapt (CMSA) matheuristic. In this study, we develop three different evolutionary approaches based on tabu search and also develop a CMSA-tabu search (CMSA-TS) hybrid. We conduct experiments on a wide range of -regular and scale-free graphs and find that, overall, CMSA-TS is the most effective approach, nearly always finding the best-observed solutions. However, in special cases where problems have large numbers of vertices and low vertex degrees, the evolutionary algorithms have a distinct advantage.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Elsevier
ISSN:	2210-6502
Date of First Compliant Deposit:	7 October 2022
Date of Acceptance:	4 October 2022
Last Modified:	08 Jan 2025 12:15
URI:	https://orca.cardiff.ac.uk/id/eprint/153131

Actions (repository staff only)

Edit Item