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

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

Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимац...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2015
Автори: Листровой, С.В., Моцный, С.В.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2015
Назва видання:Электронное моделирование
Теми:
Математическое моделирование и вычислительные методы
Онлайн доступ:http://dspace.nbuv.gov.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
id irk-123456789-101323
record_format dspace
spelling irk-123456789-1013232016-06-03T03:02:00Z Алгоритм решения задачи о наименьшем вершинном покрытии произвольного графа с помощью систем квадратичных уравнений Листровой, С.В. Моцный, С.В. Математическое моделирование и вычислительные методы Предложен алгоритм решения задачи о наименьшем покрытии произвольного графа с помощью систем квадратичных уравнений, которые позволяют достигать высокой степени распараллеливания операций. Для решения этой задачи на практике используются приближенные алгоритмы с различными коэффициентами аппроксимации. Приведены результаты экспериментального анализа, свидетельствующие о преимуществе описанного алгоритма по сравнению с существующими. Запропоновано алгоритм роз’язку задачі про найменше покриття довільного графа за допомогою систем квадратичних рівнянь, які дозволяють досягати високого ступіню розпаралелювання операцій. Для розв’язку цієї задачі на практиці використовують наближені алгоритми з різними коефіцієнтами апроксимації. Наведено результати експериментального аналізу, які свідчать про перевагу описаного алгоритму в порівнянні з існуючими. 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 http://dspace.nbuv.gov.ua/handle/123456789/101323 519.854 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
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 http://dspace.nbuv.gov.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
first_indexed 2024-03-30T08:54:18Z
last_indexed 2024-03-30T08:54:18Z
_version_ 1796148761298206720

Схожі ресурси