Expected polynomial-time randomized algorithm for graph coloring problem
From MaRDI portal
Publication:6558677
DOI10.1016/j.dam.2023.08.001zbMATH Open1541.0506MaRDI QIDQ6558677
Subhankar Ghosal, Sasthi C. Ghosh
Publication date: 20 June 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Cites Work
- Using tabu search techniques for graph coloring
- An incremental search heuristic for coloring vertices of a graph
- New integer linear programming models for the vertex coloring problem
- Coloring graphs by iterated local search traversing feasible and infeasible solutions
- Constructive generation of very hard 3-colorability instances
- A survey of local search methods for graph coloring
- A systematic study on meta-heuristic approaches for solving the graph coloring problem
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- New methods to color the vertices of a graph
- A Column Generation Approach for Graph Coloring
- Reducibility among Combinatorial Problems
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Expected polynomial-time randomized algorithm for graph coloring problem
