Finding happiness: an analysis of the maximum happy vertices problem

Lewis, R. ORCID: https://orcid.org/0000-0003-1046-811X, Thiruvady, D. and Morgan, K. 2019. Finding happiness: an analysis of the maximum happy vertices problem. Computers and Operations Research 103 10.1016/j.cor.2018.11.015

Preview

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

Abstract

The maximum happy vertices problem involves determining a vertex colouring of a graph such that the number of vertices assigned to the same colour as all of their neighbours is maximised. This problem is trivial if no vertices are precoloured, though in general it is NP-hard. In this paper we derive a number of upper and lower bounds on the number of happy vertices that are achievable in a graph and then demonstrate how certain problem instances can be broken up into smaller subproblems. Four different algorithms are also used to investigate the factors that make some problem instances more difficult to solve than others. In general, we find that the most difficult problems are those with relatively few edges and/or a small number of precoloured vertices. Ideas for future research are also discussed.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Elsevier
ISSN:	0305-0548
Date of First Compliant Deposit:	28 November 2018
Date of Acceptance:	18 November 2018
Last Modified:	08 Jan 2025 12:30
URI:	https://orca.cardiff.ac.uk/id/eprint/117168

Citation Data

Cited 17 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item