Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии
Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основе сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с в...
Gespeichert in:
| Veröffentlicht in: | Электронное моделирование |
|---|---|
| Datum: | 2012 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2012
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/61809 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862631204117807104 |
|---|---|
| author | Листровой, С.В. Минухин, С.В. |
| author_facet | Листровой, С.В. Минухин, С.В. |
| citation_txt | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии / С.В. Листровой, С.В. Минухин // Электронное моделирование. — 2012 — Т. 34, № 1. — С. 29-43. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| 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.
|
| first_indexed | 2025-11-30T10:55:20Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-61809 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-11-30T10:55:20Z |
| publishDate | 2012 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| 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 |
| spellingShingle | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии Листровой, С.В. Минухин, С.В. Математические методы и модели |
| title | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_fullStr | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_full_unstemmed | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_short | Метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| title_sort | метод решения задач о минимальном вершинном покрытии в произвольном графе и задачи о наименьшем покрытии |
| topic | Математические методы и модели |
| topic_facet | Математические методы и модели |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/61809 |
| 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 |