О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа
Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2009 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/44314 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44314 |
|---|---|
| record_format |
dspace |
| spelling |
Стецюк, П.И. Лиховид, А.П. 2013-05-28T19:35:56Z 2013-05-28T19:35:56Z 2009 О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44314 519.8 Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Про ЛП-орієнтовані верхні оцінки для зваженого числа стійкості графа LP-oriented upper bounds for the weighted stability number of a graph Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| spellingShingle |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Стецюк, П.И. Лиховид, А.П. Системный анализ |
| title_short |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_full |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_fullStr |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_full_unstemmed |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_sort |
о лп-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| author |
Стецюк, П.И. Лиховид, А.П. |
| author_facet |
Стецюк, П.И. Лиховид, А.П. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2009 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Про ЛП-орієнтовані верхні оцінки для зваженого числа стійкості графа LP-oriented upper bounds for the weighted stability number of a graph |
| description |
Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та 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.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44314 |
| citation_txt |
О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT stecûkpi olporientirovannyhverhnihocenkahdlâvzvešennogočislaustoičivostigrafa AT lihovidap olporientirovannyhverhnihocenkahdlâvzvešennogočislaustoičivostigrafa AT stecûkpi prolporíêntovaníverhníocínkidlâzvaženogočislastíikostígrafa AT lihovidap prolporíêntovaníverhníocínkidlâzvaženogočislastíikostígrafa AT stecûkpi lporientedupperboundsfortheweightedstabilitynumberofagraph AT lihovidap lporientedupperboundsfortheweightedstabilitynumberofagraph |
| first_indexed |
2025-12-01T15:40:39Z |
| last_indexed |
2025-12-01T15:40:39Z |
| _version_ |
1850860627407405056 |