Розглядаються верхні оцінки для зваженого числа стійкості графа , які базуються на апроксимації багатокутника стійких множин за дрпомогою лінійних нерівностей для непарних циклів та р-коліс в графі. Побудовано аогоритми знаходження верхніх оцінок на основі розв'язку задачі лінійного програмування зі скінченним числом нерівностей, які отримані на основі алгоритму найкоротших шляхів в спеціальному графі.
