О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / Стецюк П. И., Лиховид А. П. (2009)
web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0000466500
Cybernetics and Systems Analysis   А - 2019 /  Issue (2009, Т. 45, № 1)
Стецюк П. И., Лиховид А. П.
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Розглянуто верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на базі розв'язку задачі лінійного програмування зі скінченним числом нерівностей, які одержано на базі алгоритму найкоротших шляхів в спеціальному графі. Наведено результати тестових експериментів, коли граф містить від декількох сотень до тисячі вершин.
Бібліографічний опис:
Стецюк П. И., Лиховид А. П. О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа. Кибернетика и системный анализ. 2009. Т. 45, № 1. С. 157-170. URL: http://jnas.nbuv.gov.ua/article/UJRN-0000466500 |  Cybernetics and Systems Analysis / Issue (2009, 45 (1))
 Transliteration
Stetsjuk P. I., Likhovid A. P.
O LP-orientirovannykh verkhnikh otsenkakh dlja vzveshennogo chisla ustojchivosti grafa
Cite:
Stetsjuk, P. I., Likhovid, A. P. (2009). O LP-orientirovannykh verkhnikh otsenkakh dlja vzveshennogo chisla ustojchivosti grafa. Cybernetics and Systems Analysis, 45 (1), 157-170 http://jnas.nbuv.gov.ua/article/UJRN-0000466500 [In Russian]. | |
|
|
PDF