Finding happiness: an analysis of the maximum happy vertices problem

DOI10.1016/j.cor.2018.11.015zbMath1458.05076OpenAlexW2900685636WikidataQ128889551 ScholiaQ128889551MaRDI QIDQ1634084

Kerri Morgan, Dhananjay Thiruvady, Rhyd Lewis

Publication date: 17 December 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: http://orca.cf.ac.uk/117168/1/MHVPaper.pdf

zbMATH Keywords

integer programminggraph colouringhappy colouringproblem subdivision

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

A simple and effective algorithm for the maximum happy vertices problem ⋮ Complexity and approximability of the happy set problem ⋮ Multi-constructor CMSA for the maximum disjoint dominating sets problem ⋮ New algorithms for a simple measure of network partitioning ⋮ Parameterized algorithms for the happy set problem ⋮ Graph classes and approximability of the happy set problem ⋮ Tackling the maximum happy vertices problem in large networks ⋮ The maximum happy induced subgraph problem: bounds and algorithms ⋮ New algorithms for a simple measure of network partitioning ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Lower bounds for the happy coloring problems

Uses Software

• gCol

Cites Work

• Unnamed Item
• Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem
• Construct, Merge, Solve \& Adapt A new general algorithm for combinatorial optimization
• Algorithmic aspects of homophyly of networks
• On the parameterized complexity of happy vertex coloring
• The parameterized complexity of happy colorings
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition
• Cluster Analysis
• Finding all minimum-size separating vertex sets in a graph
• Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
• A Guide to Graph Colouring

This page was built for publication: Finding happiness: an analysis of the maximum happy vertices problem