Оптимизированный метод решения задачи о наименьшем покрытии на основе негарантированного прогнозирования
Наукові видання Харківського національного університету Повітряних Сил
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Оптимизированный метод решения задачи о наименьшем покрытии на основе негарантированного прогнозирования
Оптимізований метод рішення задачі про найменше покриття на основі негарантованого прогнозування The optimized method for solving the minimum vertex cover problems based on a non-guaranteed prediction |
|
| Creator |
С.В. Листровой
С.В. Моцный С.В. Лістровий С.В Моцний S.V. Listrovoy S.V. Motsnyi |
|
| Subject |
Математичні моделі та методи
УДК 519.854 вершинное покрытие, временная сложность, булевы функции вершинне покриття, тимчасова складність, булеві функції vertex coverage, temporal complication, functions are boole |
|
| Description |
В статье представлен оптимизированный метод решения задачи о наименьшем покрытии для произвольных графов, основанный на составлении и анализе пессимистического негарантированного прогнозирования наихудшего случая формирования выборки вершин, которые можно включить в покрытие. Рассмотрена эффективность работы данного алгоритма при использовании различных моделей построения графов. Проанализирована временная сложность, погрешность, а также рациональность использования данного метода в средах распараллеливания нагрузки и телекоммуникационных системах.
У статті представлено оптимізований метод розв'язання задачі про найменше покриття для довільних графів, заснований на складанні та аналізі песимістичного негарантованого прогнозування найгіршого випадку формування вибірки вершин, які можна включити в покриття. Розглянуто ефективність роботи даного алгоритму при використанні різних моделей побудови графів. Проаналізована тимчасова складність, похибка, а також раціональність використання даного методу в середовищах розпаралелювання навантаження і телекомунікаційних системах. In this article an optimized method for solving problems of finding the minimum vertex covers for the arbitrary graphs based on the analysis of an unwarranted pessimistic prediction of the worst-case sample of the vertices that can be included into the cover is discussed. The effectiveness of this algorithm is shown by testing the different graph models. The time complexity, measurement errors and the possible use of this technique in the distributed environments and the telecommunication systems have also been summarized. |
|
| Publisher |
Харківський національний університет Повітряних Сил ім. І. Кожедуба
Харьковский национальный университет Воздушных Сил им. И. Кожедуба Kharkiv national Air Force University named after I. Kozhedub |
|
| Date |
2015
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion Рецензована стаття |
|
| Format |
application/pdf
|
|
| Identifier |
http://www.hups.mil.gov.ua/periodic-app/article/4292
|
|
| Source |
Системи обробки інформації. — 2015. — № 1(126). 118-121
Системы обработки информации. — 2015. — № 1(126). 118-121 Information Processing Systems. — 2015. — № 1(126). 118-121 1681-7710 |
|
| Language |
rus
|
|
| Relation |
http://www.hups.mil.gov.ua/periodic-app/article/4292/soi_2015_1_29.pdf
|
|