A semidefinite programming-based heuristic for graph coloring
From MaRDI portal
Publication:2467349
DOI10.1016/J.DAM.2006.07.014zbMATH Open1235.05050OpenAlexW2043473394MaRDI QIDQ2467349FDOQ2467349
Authors: Igor Dukanovic, Franz Rendl 
Publication date: 21 January 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.014
Recommendations
- Approximate graph coloring by semidefinite programming
- New heuristics for the vertex coloring problem based on semidefinite programming
- Publication:5752591
- scientific article; zbMATH DE number 4134072
- Publication:4206748
- A heuristic for the convex recoloring problem in graphs
- scientific article; zbMATH DE number 2119717
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- scientific article
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15)
Cites Work
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A Spectral Bundle Method for Semidefinite Programming
- Title not available (Why is that?)
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Semidefinite optimization
- A boundary point method to solve semidefinite programs
- New methods to color the vertices of a graph
- Hybrid evolutionary algorithms for graph coloring
- A Column Generation Approach for Graph Coloring
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- Using tabu search techniques for graph coloring
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Solving some large scale semidefinite programs via the conjugate residual method
- Finding the chromatic number by means of critical graphs
- Chromatic Scheduling and the Chromatic Number Problem
- Genetic and hybrid algorithms for graph coloring
- Semidefinite programming in combinatorial optimization
- Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
- Genetic algorithm for graph coloring: exploration of Galinier and Hao's algorithm
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Title not available (Why is that?)
Cited In (19)
- Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling
- A NEW APPROACH TO THE VERTEX COLORING PROBLEM
- A Wide Branching Strategy for the Graph Coloring Problem
- Evolutionary Computation in Combinatorial Optimization
- A parallel lagrangian heuristic for the fractional chromatic number of a graph
- Title not available (Why is that?)
- A search space ``cartography for guiding graph coloring heuristics
- New heuristics for the vertex coloring problem based on semidefinite programming
- Copositive programming motivated bounds on the stability and the chromatic numbers
- Solving graph coloring problems with the Douglas-Rachford algorithm
- Title not available (Why is that?)
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Models and heuristic algorithms for a weighted vertex coloring problem
- An optimal greedy heuristic to color interval graphs
- Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks
- Improving graph colouring algorithms and heuristics using a novel representation
- Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
- The Operator $\Psi$ for the Chromatic Number of a Graph
- Title not available (Why is that?)
Uses Software
This page was built for publication: A semidefinite programming-based heuristic for graph coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467349)
