Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений

• Опубліковано в: : Электронное моделирование
• Дата: 2015
• Автори: Листровой, С.В., Моцный, С.В.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 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 назв. — рос.

Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими. Запропоновано алгоритм роз’язку задачі про найменше покриття довільного графа за допомогою систем квадратичних рівнянь, які дозволяють досягати високого ступіню розпаралелювання операцій. Для розв’язку цієї задачі на практиці використовують наближені алгоритми з різними коефіцієнтами апроксимації. Наведено результати експериментального аналізу, які свідчать про перевагу описаного алгоритму в порівнянні з існуючими. 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.