Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений
Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимац...
Saved in:
| Date: | 2015 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2015
|
| Series: | Электронное моделирование |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101323 |
| 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: | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101323 |
|---|---|
| record_format |
dspace |
| fulltext |
|
| spelling |
nasplib_isofts_kiev_ua-123456789-1013232025-02-09T12:16:22Z Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений The minimum vertex cover problem solving algorithm for an arbitrary graph with using the systems of quadratic equations Листровой, С.В. Моцный, С.В. Математическое моделирование и вычислительные методы Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими. Запропоновано алгоритм роз’язку задачі про найменше покриття довільного графа за допомогою систем квадратичних рівнянь, які дозволяють досягати високого ступіню розпаралелювання операцій. Для розв’язку цієї задачі на практиці використовують наближені алгоритми з різними коефіцієнтами апроксимації. Наведено результати експериментального аналізу, які свідчать про перевагу описаного алгоритму в порівнянні з існуючими. This paper presents an algorithm for solving the minimum vertex cover problem for the arbitrary graphs using systems of quadratic equations that provide high level of the operations parallelization. Approximation algorithms with different approximation coefficients can be used in practice to solve such problems. Experimental analysis shows the advantages of the described methodology in comparison with existing implementations. The algorithm effectiveness can be significantly enhanced by the use of distributed systems with many cores. 2015 Article Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101323 519.854 ru Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы |
| spellingShingle |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы Листровой, С.В. Моцный, С.В. Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений Электронное моделирование |
| description |
Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими. |
| format |
Article |
| author |
Листровой, С.В. Моцный, С.В. |
| author_facet |
Листровой, С.В. Моцный, С.В. |
| author_sort |
Листровой, С.В. |
| title |
Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_short |
Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_full |
Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_fullStr |
Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_full_unstemmed |
Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_sort |
алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2015 |
| topic_facet |
Математическое моделирование и вычислительные методы |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101323 |
| citation_txt |
Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT listrovojsv algoritmrešeniâzadačionaimenʹšemveršinnompokrytiiproizvolʹnogografaspomoŝʹûsistemkvadratičnyhuravnenij AT mocnyjsv algoritmrešeniâzadačionaimenʹšemveršinnompokrytiiproizvolʹnogografaspomoŝʹûsistemkvadratičnyhuravnenij AT listrovojsv theminimumvertexcoverproblemsolvingalgorithmforanarbitrarygraphwithusingthesystemsofquadraticequations AT mocnyjsv theminimumvertexcoverproblemsolvingalgorithmforanarbitrarygraphwithusingthesystemsofquadraticequations |
| first_indexed |
2025-11-25T23:07:30Z |
| last_indexed |
2025-11-25T23:07:30Z |
| _version_ |
1849805557350793216 |