On the fractional chromatic number of monotone self-dual Boolean functions
On the fractional chromatic number of monotone self-dual Boolean functions
复制标题
DOI：
10.1016/j.disc.2008.01.028
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
D. Gaur;K. Makino
中科院分区：
文献类型：
--
作者：
D. Gaur;K. Makino
我们计算了几类单调自对偶布尔函数的精确分数色数。我们根据色数的标准IP公式的适当加强的Lp松弛的最佳值来刻画单调自对偶布尔函数。我们还证明了判定单调布尔函数的自对偶等价于判定隐式定义的多面体中某一点的可行性。
We compute the exact fractional chromatic number for several classes of monotone self-dual Boolean functions. We characterize monotone self-dual Boolean functions in terms of the optimal value of an LP relaxation of a suitable strengthening of the standard IP formulation for the chromatic number. We also show that determining the self-duality of a monotone Boolean function is equivalent to determining the feasibility of a certain point in a polytope defined implicitly.