Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа
Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное вр...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2017
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/127559 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-127559 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1275592017-12-25T03:02:25Z Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Математическое моделирование и вычислительные методы Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное время. При дальнейшем увеличении числа вершин и уменьшении плотности ребер в графе алгоритм имеет экспоненциальную сложность, которая имеет тенденцию к уменьшению при увеличении плотности ребер в графе, где n — число вершин графа. Запропоновано метод пошуку найбільших максимальних незалежних множин неорієнтованого зв’язкового графа, який дозволяє при числі вершин в графі, що не перевищує 120, і щільності ребер у діапазоні від 0,067 до 0,9, вирішувати задачу визначення найбільших максимальних незалежних множин за поліноміальний час. При подальшому збільшенні числа вершин і зменшенні щільності ребер в графі алгоритм має експоненціальну складність, яка має тенденцію до зменшення при збільшенні щільності ребер в графі, де n — число вершин графа. A method of search for the largest maximal independent sets of an undirected connected graph is proposed that allows one to solve the problem of determining the largest maximal independent sets in polynomial time with the number of vertices in the graph not exceeding 120 and the density of edges in the range from 0.067 to 0.9. with a further increase in the number of vertices and a decrease in the density of edges in the graph, the algorithm has an exponential complexity, which tends to the decrease with increasing the edge density in the graph, where n is the number of vertices in the graph. 2017 Article Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/127559 519.682.1 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы |
| spellingShingle |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа Электронное моделирование |
| description |
Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное время. При дальнейшем увеличении числа вершин и уменьшении плотности ребер в графе алгоритм имеет экспоненциальную сложность, которая имеет тенденцию к уменьшению при увеличении плотности ребер в графе, где n — число вершин графа. |
| 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/127559 |
| citation_txt |
Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT listrovojsv metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT sidorenkoav metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT listrovaâes metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa |
| first_indexed |
2023-10-18T20:53:21Z |
| last_indexed |
2023-10-18T20:53:21Z |
| _version_ |
1796151372057411584 |