Об одной верхней оценке для взвешенного числа устойчивости графа

Abstract

We derived an upper bound for the weighted stability number of a simple undirected graph G, which is the solution of a linear pogramming problem with O(|V|³) constraints, where V is a number of vertices in the graph. We proved that this upper bound is at least as good as the known bound based on the polytope CSTAB(G) , and it is also an exact upper bound for the weighted stability number of the t-perfect graph.