Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа
Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное вр...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2017 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2017
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/127559 |
| 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, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862543103519358976 |
|---|---|
| author | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| author_facet | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. |
| citation_txt | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 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.
|
| first_indexed | 2025-11-24T20:24:03Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-127559 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-24T20:24:03Z |
| publishDate | 2017 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. 2017-12-24T09:41:46Z 2017-12-24T09:41:46Z 2017 Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 3. — С. 17-35. — Бібліогр.: 27 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/127559 519.682.1 Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 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. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа The method of determining the largest maximal independent sets of vertices of undirected graph Article published earlier |
| spellingShingle | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. Математическое моделирование и вычислительные методы |
| title | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_alt | The method of determining the largest maximal independent sets of vertices of undirected graph |
| title_full | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_fullStr | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_full_unstemmed | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_short | Метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| title_sort | метод поиска наибольших максимальных независимых множеств вершин неориентированного графа |
| topic | Математическое моделирование и вычислительные методы |
| topic_facet | Математическое моделирование и вычислительные методы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/127559 |
| work_keys_str_mv | AT listrovoisv metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT sidorenkoav metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT listrovaâes metodpoiskanaibolʹšihmaksimalʹnyhnezavisimyhmnožestvveršinneorientirovannogografa AT listrovoisv themethodofdeterminingthelargestmaximalindependentsetsofverticesofundirectedgraph AT sidorenkoav themethodofdeterminingthelargestmaximalindependentsetsofverticesofundirectedgraph AT listrovaâes themethodofdeterminingthelargestmaximalindependentsetsofverticesofundirectedgraph |