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: 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
Item availability restricted.

[thumbnail of RecomHappy.pdf] PDF - Accepted Post-Print Version
Restricted to Repository staff only until 17 October 2023 due to copyright restrictions.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB)

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: 24 Nov 2022 01:00
URI: https://orca.cardiff.ac.uk/id/eprint/153131

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics