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 iD for Thiruvady, D. orcid.org/0000-0002-8011-933X
Morgan, K.ORCID iD for 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

Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 23 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.