Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Recombinative approaches for the maximum happy vertices problem

Thiruvady, Dhananjay and Lewis, Rhyd ORCID: 2022. Recombinative approaches for the maximum happy vertices problem. Swarm and Evolutionary Computation 75 , 101188. 10.1016/j.swevo.2022.101188

[thumbnail of RecomHappy.pdf]
PDF - Accepted Post-Print Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB) | Preview


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: 13 Apr 2024 08:11

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics