1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 1(126)'2015
  5. Оптимізований метод рішення задачі про найменше покриття на основі негарантованого прогнозування

Оптимізований метод рішення задачі про найменше покриття на основі негарантованого прогнозування

С.В. Лістровий, С.В Моцний
Анотації на мовах:

У статті представлено оптимізований метод розв'язання задачі про найменше покриття для довільних графів, заснований на складанні та аналізі песимістичного негарантованого прогнозування найгіршого випадку формування вибірки вершин, які можна включити в покриття. Розглянуто ефективність роботи даного алгоритму при використанні різних моделей побудови графів. Проаналізована тимчасова складність, похибка, а також раціональність використання даного методу в середовищах розпаралелювання навантаження і телекомунікаційних системах.
Ключові слова: вершинне покриття, тимчасова складність, булеві функції