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

Finding happiness: An analysis of the maximum happy vertices problem

Lewis, Rhyd, Thiruvady, D. and Morgan, K. 2019. Finding happiness: An analysis of the maximum happy vertices problem. Computers and Operations Research 103 , p. 265. 10.1016/j.cor.2018.11.015
Item availability restricted.

[img] PDF - Accepted Post-Print Version
Restricted to Repository staff only until 22 November 2019 due to copyright restrictions.

Download (908kB)

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: 03 Jul 2019 10:41
URI: http://orca.cf.ac.uk/id/eprint/117168

Citation Data

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

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics