The Maximum Happy Induced Subgraph Problem: Bounds and Algorithms Lewis, R., Thiruvady, D. and Morgan, K. 2021, The Maximum Happy Induced Subgraph Problem: Bounds and Algorithms, Computers and Operations Research, vol. 126, pp. 1-15, doi: 10.1016/j.cor.2020.105114. Attached Files Name Description MIMEType Size Downloads Title The Maximum Happy Induced Subgraph Problem: Bounds and Algorithms Author(s) Lewis, R. Thiruvady, D. orcid.org/0000-0002-8011-933X Morgan, K. orcid.org/0000-0002-7263-8340 Journal name Computers and Operations Research Volume number 126 Article ID 105114 Start page 1 End page 15 Total pages 15 Publisher Elsevier Place of publication Amsterdam, The Netherlands Publication date 2021 ISSN 0305-0548 Keyword(s) Graph colouring Combinatorial optimisation Vertex cut sets Tabu search Summary In this paper we consider a combinatorial optimisation problem that takes as input a graph in which some of the vertices have been preassigned to colours. The aim is to then identify the largest induced subgraph in which all remaining vertices are able to assume the same colour as all of their neighbours. This problem shares similarities with the graph colouring problem, vertex cut problems, and the maximum happy vertices problem. It is NP-hard in general. In this paper we derive a number of upper and lower bounds and also show how certain problem instances can be broken up into smaller subproblems. We also propose one exact and two heuristic algorithms for this problem and use these to investigate the factors that make some problem instances more difficult to solve than others. Language eng DOI 10.1016/j.cor.2020.105114 Indigenous content off Field of Research 0102 Applied Mathematics 0103 Numerical and Computational Mathematics HERDC Research category C1 Refereed article in a scholarly journal Persistent URL http://hdl.handle.net/10536/DRO/DU:30143883 Document type: Journal Article Collections: Faculty of Science, Engineering and Built Environment School of Information Technology Related Links Link Description Connect to published version Go to link with your DU access privileges     Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved. Versions Version Filter Type Sat, 10 Oct 2020, 15:18:18 EST Sun, 11 Oct 2020, 04:00:32 EST Mon, 12 Oct 2020, 07:01:05 EST Mon, 12 Oct 2020, 13:14:05 EST Tue, 20 Oct 2020, 05:04:43 EST Tue, 20 Oct 2020, 13:12:27 EST Tue, 20 Oct 2020, 13:14:15 EST Tue, 20 Oct 2020, 14:48:44 EST Sat, 31 Oct 2020, 01:38:10 EST Sat, 09 Jan 2021, 01:35:09 EST Filtered Full Citation counts:   Cited 0 times in TR Web of Science Cited 0 times in Scopus Search Google Scholar Access Statistics: 73 Abstract Views, 0 File Downloads  -  Detailed Statistics Created: Mon, 12 Oct 2020, 13:14:05 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.