О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа
Розглядаються верхні оцінки для зваженого числа стійкості графа, які базуються на апроксимації багатокутника стійких множин за допомогою лінійних нерівностей для непарних циклів та p-коліс в графі. Побудовано алгоритми знаходження верхніх оцінок на основі розв’язку задачі лінійного програмування зі...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44314 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862649677245054976 |
|---|---|
| author | Стецюк, П.И. Лиховид, А.П. |
| author_facet | Стецюк, П.И. Лиховид, А.П. |
| citation_txt | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа / П.И. Стецюк, А.П. Лиховид // Кибернетика и системный анализ. — 2009. — № 1. — С. 157-170. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| 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.
|
| first_indexed | 2025-12-01T15:40:39Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-44314 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T15:40:39Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа Стецюк, П.И. Лиховид, А.П. Системный анализ |
| title | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_alt | Про ЛП-орієнтовані верхні оцінки для зваженого числа стійкості графа LP-oriented upper bounds for the weighted stability number of a graph |
| title_full | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_fullStr | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_full_unstemmed | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_short | О ЛП-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| title_sort | о лп-ориентированных верхних оценках для взвешенного числа устойчивости графа |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44314 |
| 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 |