论文标题
基于0-1二次优化的稳定设定和着色边界
Stable-Set and Coloring bounds based on 0-1 quadratic optimization
论文作者
论文摘要
我们考虑稳定和着色的半芬矿松弛，这些放松基于二次的0-1优化。有关稳定数和色数的信息隐藏在目标函数中。这导致简化的松弛，这主要取决于图形的顶点。我们还提出了基于底层图的最大簇的松弛的收紧。文献图表上的计算结果表明了这种新方法的强大潜力。
We consider semidefinite relaxations of Stable-Set and Coloring, which are based on quadratic 0-1 optimization. Information about the stability number and the chromatic number is hidden in the objective function. This leads to simplified relaxations which depend mostly on the number of vertices of the graph. We also propose tightenings of the relaxations which are based on the maximal cliques of the underlying graph. Computational results on graphs from the literature show the strong potential of this new approach.
