Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии
Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с в...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/61809 |
| 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: | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-61809 |
|---|---|
| record_format |
dspace |
| spelling |
Листровой, С.В. Минухин, С.В. 2014-05-11T17:40:56Z 2014-05-11T17:40:56Z 2012 Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/61809 519.682.1 Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей О (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. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математические методы и модели Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| spellingShingle |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии Листровой, С.В. Минухин, С.В. Математические методы и модели |
| title_short |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_fullStr |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full_unstemmed |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_sort |
метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| author |
Листровой, С.В. Минухин, С.В. |
| author_facet |
Листровой, С.В. Минухин, С.В. |
| topic |
Математические методы и модели |
| topic_facet |
Математические методы и модели |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| description |
Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей О (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.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/61809 |
| citation_txt |
Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
| work_keys_str_mv |
AT listrovoisv metodrešeniâzadačominimalʹnomveršinnompokrytiivproizvolʹnomgrafeizadačionaimenʹšempokrytii AT minuhinsv metodrešeniâzadačominimalʹnomveršinnompokrytiivproizvolʹnomgrafeizadačionaimenʹšempokrytii |
| first_indexed |
2025-11-30T10:55:20Z |
| last_indexed |
2025-11-30T10:55:20Z |
| _version_ |
1850857378587607041 |