Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений
Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимац...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2015 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101323 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862561636101914624 |
|---|---|
| author | Листровой, С.В. Моцный, С.В. |
| author_facet | Листровой, С.В. Моцный, С.В. |
| citation_txt | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими.
Запропоновано алгоритм роз’язку задачі про найменше покриття довільного графа за допомогою систем квадратичних рівнянь, які дозволяють досягати високого ступіню розпаралелювання операцій. Для розв’язку цієї задачі на практиці використовують наближені алгоритми з різними коефіцієнтами апроксимації. Наведено результати експериментального аналізу, які свідчать про перевагу описаного алгоритму в порівнянні з існуючими.
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.
|
| first_indexed | 2025-11-25T23:07:30Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-101323 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-25T23:07:30Z |
| publishDate | 2015 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Листровой, С.В. Моцный, С.В. 2016-06-02T14:40:32Z 2016-06-02T14:40:32Z 2015 Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений / С.В. Листровой, С.В. Моцный // Электронное моделирование. — 2015. — Т. 37, № 6. — С. 3-17. — Бібліогр.: 12 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101323 519.854 Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими. Запропоновано алгоритм роз’язку задачі про найменше покриття довільного графа за допомогою систем квадратичних рівнянь, які дозволяють досягати високого ступіню розпаралелювання операцій. Для розв’язку цієї задачі на практиці використовують наближені алгоритми з різними коефіцієнтами апроксимації. Наведено результати експериментального аналізу, які свідчать про перевагу описаного алгоритму в порівнянні з існуючими. 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. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений The minimum vertex cover problem solving algorithm for an arbitrary graph with using the systems of quadratic equations Article published earlier |
| spellingShingle | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений Листровой, С.В. Моцный, С.В. Математическое моделирование и вычислительные методы |
| title | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_alt | The minimum vertex cover problem solving algorithm for an arbitrary graph with using the systems of quadratic equations |
| title_full | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_fullStr | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_full_unstemmed | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_short | Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| title_sort | алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений |
| topic | Математическое моделирование и вычислительные методы |
| topic_facet | Математическое моделирование и вычислительные методы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101323 |
| work_keys_str_mv | AT listrovoisv algoritmrešeniâzadačionaimenʹšemveršinnompokrytiiproizvolʹnogografaspomoŝʹûsistemkvadratičnyhuravnenii AT mocnyisv algoritmrešeniâzadačionaimenʹšemveršinnompokrytiiproizvolʹnogografaspomoŝʹûsistemkvadratičnyhuravnenii AT listrovoisv theminimumvertexcoverproblemsolvingalgorithmforanarbitrarygraphwithusingthesystemsofquadraticequations AT mocnyisv theminimumvertexcoverproblemsolvingalgorithmforanarbitrarygraphwithusingthesystemsofquadraticequations |