Tackling the maximum happy vertices problem in large networks

DOI10.1007/s10288-020-00431-4zbMath1462.68148OpenAlexW3007553927MaRDI QIDQ2026712

Dhananjay Thiruvady, Rhyd Lewis, Kerri Morgan

Publication date: 20 May 2021

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://orca.cardiff.ac.uk/129862/1/MHVTabu.pdf

zbMATH Keywords

tabu searchgraph colouringmaximum happy vertices problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

New algorithms for a simple measure of network partitioning

Uses Software

• Tabu search
• gCol

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem
• Algorithmic aspects of homophyly of networks
• Graph colouring approaches for a satellite range scheduling problem
• On a parallel genetic-tabu search based algorithm for solving the graph colouring problem
• Finding happiness: an analysis of the maximum happy vertices problem
• On the parameterized complexity of happy vertex coloring
• Improved approximation algorithms for the maximum happy vertices and edges problems
• A graph coloring heuristic using partial solutions and a reactive tabu scheme
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition
• Cluster Analysis