Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment

DOI10.1051/ro:2001112zbMath1049.90111OpenAlexW2018052030MaRDI QIDQ2773169

Philippe Meurdesoif, Benoît Rottembourg

Publication date: 2001

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2001__35_2_211_0

zbMATH Keywords

semidefinite programminggraph coloringdiscrete optimizationfrequency assignmenthypergraph coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Coloring of graphs and hypergraphs (05C15)

Uses Software

• SDPpack

Cites Work

• Zero knowledge and the chromatic number
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• On the hardness of approximating minimization problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Semi-Definite positive Programming Relaxations for Graph K_n-Coloring in Frequency Assignment