О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / Стецюк П. И., Лиховид А. П. (2009)
Ukrainian

інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0000466500
  Кибернетика и системный анализ      А - 2019  /     Випуск (2009, Т. 45, № 1)

Стецюк П. И., Лиховид А. П.
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа

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

Бібліографічний опис:
Стецюк П. И., Лиховид А. П. О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа. Кибернетика и системный анализ. 2009. Т. 45, № 1. С. 157-170. URL: http://jnas.nbuv.gov.ua/article/UJRN-0000466500

English  Cybernetics and Systems Analysis   /     Issue (2009, 45 (1))

translit 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].

 

Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна