An incremental search heuristic for coloring vertices of a graph
type: Item
instance of: scholarly article
title: An incremental search heuristic for coloring vertices of a graph
zbMATH Open document ID: 1491.05077
DOI: 10.1007/978-3-030-63072-0_4
author: Subhankar Ghosal
author: Sasthi C. Ghosh
publication date: 2021-12-08T00:00:00Z
review text: In this paper, the authors propose an incremental search heuristic (ISH) method for vertex coloring. First, they expound on the greedy coloring by predecessors and list several good orders of vertices for coloring. Then, the authors prove several related theorems about coloring order, by which an algorithm framework ISH is developed. The algorithm is simple and fast. On small sparse graphs, the algorithm can obtain the same or even a few smaller chromatic numbers than other classical algorithms. However, compared with the hybrid genetic algorithm, the accuracy of the algorithm needs to be improved. The algorithm only achieved a smaller chromatic number on one test set, while the genetic algorithm achieved a smaller chromatic number on six test sets. For the entire collection see [Zbl 1465.05002].
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C42
zbMATH DE Number: 7440727
zbMATH Keywords: vertex coloring
zbMATH Keywords: heuristic algorithm
reviewed by: Enqiang Zhu
MaRDI profile type: Publication
full work available at URL: 978-3-030-63072-0 4
OpenAlex ID: W3135450210
cites work: Reducibility among Combinatorial Problems
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
cites work: A survey of local search methods for graph coloring
cites work: Q4247451
cites work: An upper bound for the chromatic number of a graph and its application to timetabling problems
cites work: New methods to color the vertices of a graph
cites work: Some experiments with simulated annealing for coloring graphs
cites work: Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
cites work: A memetic algorithm for graph coloring
cites work: Q4352217
cites work: Using tabu search techniques for graph coloring
cites work: The chromatic number of random graphs
cites work: Constructive generation of very hard 3-colorability instances
cites work: Coloring graphs by iterated local search traversing feasible and infeasible solutions
cites work: Q5687261
cites work: A Column Generation Approach for Graph Coloring
cites work: New integer linear programming models for the vertex coloring problem
cites work: An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
cites work: A systematic study on meta-heuristic approaches for solving the graph coloring problem
description: scientific article; zbMATH DE number 7440727