О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа
Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/44314 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-44314 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-443142013-05-29T03:08:48Z О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Стецюк, П.И. Лиховид, А.П. Системный анализ Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі скінченним числом нерівностей, які отримані на основі алгоритму найкоротших шляхів в спеціальному графі. Наведено результати тестових експериментів, коли граф містить від декількох сотень до тисячі вершин. Upper bounds are considered for the weighted stability number of a graph that are based on the approximation of the polytope of stable sets by linear inequalities for odd cycles and p-wheels in the graph. Algorithms are developed for finding upper bounds on the basis of solution of an LP-problem with a finite number of inequalities produced by the shortest path algorithm for a special graph. The results of test experiments are given for graphs with several hundred or thousand nodes. 2009 Article О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/44314 519.8 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Стецюк, П.И. Лиховид, А.П. О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Кибернетика и системный анализ |
| description |
Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі скінченним числом нерівностей, які отримані на основі алгоритму найкоротших шляхів в спеціальному графі. Наведено результати тестових експериментів, коли граф містить від декількох сотень до тисячі вершин. |
| format |
Article |
| author |
Стецюк, П.И. Лиховид, А.П. |
| author_facet |
Стецюк, П.И. Лиховид, А.П. |
| author_sort |
Стецюк, П.И. |
| title |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_short |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_full |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_fullStr |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_full_unstemmed |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_sort |
о лп-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2009 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/44314 |
| citation_txt |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT stecûkpi olporientirovannyhverhnihocenkahdlâvzvešennogočislaustojčivostigrafa AT lihovidap olporientirovannyhverhnihocenkahdlâvzvešennogočislaustojčivostigrafa |
| first_indexed |
2023-10-18T18:00:06Z |
| last_indexed |
2023-10-18T18:00:06Z |
| _version_ |
1796143056677765120 |