Метод перечисления максимальных независимых множеств в неориентированных графах
На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125....
Збережено в:
| Дата: | 2017 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2017
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/127632 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-127632 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1276322017-12-25T03:02:49Z Метод перечисления максимальных независимых множеств в неориентированных графах Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Математическое моделирование и вычислительные методы На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей 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. 2017 Article Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/127632 519.682.1 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы |
| spellingShingle |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Метод перечисления максимальных независимых множеств в неориентированных графах Электронное моделирование |
| description |
На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125. |
| format |
Article |
| author |
Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| author_facet |
Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| author_sort |
Листровой, С.В. |
| title |
Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_short |
Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_full |
Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_fullStr |
Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_full_unstemmed |
Метод перечисления максимальных независимых множеств в неориентированных графах |
| title_sort |
метод перечисления максимальных независимых множеств в неориентированных графах |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2017 |
| topic_facet |
Математическое моделирование и вычислительные методы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/127632 |
| citation_txt |
Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT listrovojsv metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT sidorenkoav metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT listrovaâes metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah |
| first_indexed |
2023-10-18T20:53:31Z |
| last_indexed |
2023-10-18T20:53:31Z |
| _version_ |
1796151379805339648 |