图的κ-覆盖与Grbner基求解

Solving the k-covering Problem of Graphs by Grbner Bases

证明图的k-覆盖存在性问题等价于一个多元多项式方程组在{0,1}范围的求解问题,并通过使用Grbner基给出一个图有k-覆盖的有效判别与求解方法,进而求得图的覆盖数和极小覆盖.

This paper shows that the existence of k-coverings of a graph is equivalent to the existence of solutions of a certain system of polynomial equations.Effective methods of checking the existence of k-covering and finding k-coverings,and consequently obtaining minimal coverings as well as the covering number,are given in terms of Grobner bases.