Эвристический алгоритм для поиска наибольшего независимого множества
Розроблено евристичний алгоритм для розв’язання задачі пошуку найбільшої незалежної множини вершин в неорієнтованому графі. Для цього використано підхід скінченних частково впорядкованих множин, зокрема техніка розбиття такої множини на мінімальне число ланцюгів. Побудовано спеціальний орграф, i на...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84142 |
| 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: | Эвристический алгоритм для поиска наибольшего независимого множества / А.Д. Плотников // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 41-48. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862573636855005184 |
|---|---|
| author | Плотников, А.Д. |
| author_facet | Плотников, А.Д. |
| citation_txt | Эвристический алгоритм для поиска наибольшего независимого множества / А.Д. Плотников // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 41-48. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розроблено евристичний алгоритм для розв’язання задачі пошуку найбільшої незалежної множини вершин в неорієнтованому графі. Для цього використано підхід скінченних частково впорядкованих множин, зокрема техніка розбиття такої множини на мінімальне число ланцюгів. Побудовано спеціальний орграф, i на ocнові гіпотези про його властивості запропоновано розв’язувальний алгоритм. Наведено дані експериментів на відомих прикладах.
A heuristic algorithm is developed for finding the maximum independent set of vertices in an undirected graph. To this end, the technique of finite partially ordered sets is used, in particular, the technique of partitioning such a set into the minimum number of chains. A special digraph is constructed and a solution algorithm is proposed on the basis of the hypothesis about its properties. Some experimental data are presented for well-known examples
|
| first_indexed | 2025-11-26T07:55:18Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84142 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-26T07:55:18Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Плотников, А.Д. 2015-07-03T10:01:19Z 2015-07-03T10:01:19Z 2012 Эвристический алгоритм для поиска наибольшего независимого множества / А.Д. Плотников // Кибернетика и системный анализ. — 2012. — Т. 48, № 5. — С. 41-48. — Бібліогр.: 6 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84142 519.14 Розроблено евристичний алгоритм для розв’язання задачі пошуку найбільшої незалежної множини вершин в неорієнтованому графі. Для цього використано підхід скінченних частково впорядкованих множин, зокрема техніка розбиття такої множини на мінімальне число ланцюгів. Побудовано спеціальний орграф, i на ocнові гіпотези про його властивості запропоновано розв’язувальний алгоритм. Наведено дані експериментів на відомих прикладах. A heuristic algorithm is developed for finding the maximum independent set of vertices in an undirected graph. To this end, the technique of finite partially ordered sets is used, in particular, the technique of partitioning such a set into the minimum number of chains. A special digraph is constructed and a solution algorithm is proposed on the basis of the hypothesis about its properties. Some experimental data are presented for well-known examples ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Эвристический алгоритм для поиска наибольшего независимого множества Евристичний алгоритм для пошуку найбільшої незалежної множини Heuristic algorithm for finding the maximum independent set Article published earlier |
| spellingShingle | Эвристический алгоритм для поиска наибольшего независимого множества Плотников, А.Д. Кибернетика |
| title | Эвристический алгоритм для поиска наибольшего независимого множества |
| title_alt | Евристичний алгоритм для пошуку найбільшої незалежної множини Heuristic algorithm for finding the maximum independent set |
| title_full | Эвристический алгоритм для поиска наибольшего независимого множества |
| title_fullStr | Эвристический алгоритм для поиска наибольшего независимого множества |
| title_full_unstemmed | Эвристический алгоритм для поиска наибольшего независимого множества |
| title_short | Эвристический алгоритм для поиска наибольшего независимого множества |
| title_sort | эвристический алгоритм для поиска наибольшего независимого множества |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84142 |
| work_keys_str_mv | AT plotnikovad évrističeskiialgoritmdlâpoiskanaibolʹšegonezavisimogomnožestva AT plotnikovad evrističniialgoritmdlâpošukunaibílʹšoínezaležnoímnožini AT plotnikovad heuristicalgorithmforfindingthemaximumindependentset |