Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии
Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с в...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2012
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/61809 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-61809 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-618092014-05-12T03:01:54Z Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии Листровой, С.В. Минухин, С.В. Математические методы и модели Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей О (mn²), где в случае решения ЗНВП в произвольных графах n — число вершин, а m — число ребер в графе, а в случае решения ЗНП n — число столбцов, а m — число строк в матрице В. Показано, что погрешность решения этих задач предложенными процедурами А₁ и А₂ не превышает 5 % при плотности строк матрицы В, равной 0,5 и более. Запропоновано наближені алгоритми розв’язування задачі про найменше вершинне покриття (ЗНВП) у довільних графах і задачі про найменше покриття (ЗНП), базовані на зведенні їх відповідно до задач квадратичного та нелінійного булевого програмування, специфіка яких дозволила побудувати алгоритми з часовою складністю, що не перевищує О (mn²), де у випадку розв’язування ЗНВП у довільних графах n — число вершин, а m — число ребер у графі, а при розв’язуванні ЗНП n — число стовпців, а m — число рядків у матриці В. Показано, що похибка розв’язку цих задач запропонованими процедурами А₁ і А₂ не перевищує 5 % при густині рядків матриці В, що дорівнює 0,5 і більше. The authors propose approximate algorithms for solving the problem of the minimal vertex covering of arbitrary graphs and the problem of minimal coverage on the basis of their reduction, respectively, to the problems of quadratic and nonlinear Boolean programming, their specificity allowing to construct algorithms with time complexity not exceeding O (mn²), where in the case of solving the problem of minimal vertex covering of arbitrary graphs n is the number of vertices in the graph, m is the number of edges in the graph, and in the case of solving the problem of minimal coverage n is the number of columns in the matrix, m is the number of rows in B. It is shown that this error in the solution of these problems by the proposed procedures A₁ and A₂ does not exceed 5 % at the density of rows of B matrix 0.5 or more. 2012 Article Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/61809 519.682.1 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математические методы и модели Математические методы и модели |
| spellingShingle |
Математические методы и модели Математические методы и модели Листровой, С.В. Минухин, С.В. Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии Электронное моделирование |
| description |
Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей О (mn²), где в случае решения ЗНВП в произвольных графах n — число вершин, а m — число ребер в графе, а в случае решения ЗНП n — число столбцов, а m — число строк в матрице В. Показано, что погрешность решения этих задач предложенными процедурами А₁ и А₂ не превышает 5 % при плотности строк матрицы В, равной 0,5 и более. |
| format |
Article |
| author |
Листровой, С.В. Минухин, С.В. |
| author_facet |
Листровой, С.В. Минухин, С.В. |
| author_sort |
Листровой, С.В. |
| title |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_short |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_fullStr |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full_unstemmed |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_sort |
метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2012 |
| topic_facet |
Математические методы и модели |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/61809 |
| citation_txt |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT listrovojsv metodrešeniâzadačominimalʹnomveršinnompokrytiivproizvolʹnomgrafeizadačionaimenʹšempokrytii AT minuhinsv metodrešeniâzadačominimalʹnomveršinnompokrytiivproizvolʹnomgrafeizadačionaimenʹšempokrytii |
| first_indexed |
2023-10-18T18:39:45Z |
| last_indexed |
2023-10-18T18:39:45Z |
| _version_ |
1796144819271106560 |