Метод перечисления максимальных независимых множеств в неориентированных графах
На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125....
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2017 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2017
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/127632 |
| 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: | Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862623409066737664 |
|---|---|
| author | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| author_facet | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| citation_txt | Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125.
На основі рангового підходу запропоновано метод перерахування максимальних незалежних множин неорієнтованого зв’язного графа з часовою складністю, що в середньому не перевищує O (n⁶), де n — число вершин у графі, для графів, що не мають розділяючих вершин, розмір яких не перевищує n = 125.
Based on the rank approach the authors propose a method of enumeration of maximum independent sets of nonoriented connected graph with time complexity that does not exceed, at an average, O (n⁶), where n is the number of vertices in the graph, for the graphs which do not contain separating vertices, which dimension does not exceed n=125.
|
| first_indexed | 2025-12-07T13:29:37Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-127632 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T13:29:37Z |
| publishDate | 2017 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. 2017-12-24T11:14:28Z 2017-12-24T11:14:28Z 2017 Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/127632 519.682.1 На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125. На основі рангового підходу запропоновано метод перерахування максимальних незалежних множин неорієнтованого зв’язного графа з часовою складністю, що в середньому не перевищує O (n⁶), де n — число вершин у графі, для графів, що не мають розділяючих вершин, розмір яких не перевищує n = 125. Based on the rank approach the authors propose a method of enumeration of maximum independent sets of nonoriented connected graph with time complexity that does not exceed, at an average, O (n⁶), where n is the number of vertices in the graph, for the graphs which do not contain separating vertices, which dimension does not exceed n=125. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Метод перечисления максимальных независимых множеств в неориентированных графах Method of enumeration of maximum independent sets in nonoriented graphs Article published earlier |
| spellingShingle | Метод перечисления максимальных независимых множеств в неориентированных графах Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Математическое моделирование и вычислительные методы |
| title | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_alt | Method of enumeration of maximum independent sets in nonoriented graphs |
| title_full | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_fullStr | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_full_unstemmed | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_short | Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_sort | метод перечисления максимальных независимых множеств в неориентированных графах |
| topic | Математическое моделирование и вычислительные методы |
| topic_facet | Математическое моделирование и вычислительные методы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/127632 |
| work_keys_str_mv | AT listrovoisv metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT sidorenkoav metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT listrovaâes metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT listrovoisv methodofenumerationofmaximumindependentsetsinnonorientedgraphs AT sidorenkoav methodofenumerationofmaximumindependentsetsinnonorientedgraphs AT listrovaâes methodofenumerationofmaximumindependentsetsinnonorientedgraphs |