Предложены приближенные алгоритмы решения задачи о наименьшем вершинном покрытии (ЗНВП) в произвольных графах и задачи о наименьшем покрытии (ЗНП) на основании сведения их соответственно к задачам квадратичного и нелинейного булевого программирования, специфика которых позволила построить алгоритмы с временной сложностью, не превышающей O(mn<^>2), где в случае решения ЗНВП в произвольных графах n - число вершин, а m - число ребер в графе, а в случае решения ЗНП n - число столбцов, а m - число строк в матрице B. Показано, что погрешность решения этих задач предложенными процедурами A1 и A2 не превышает 5 % при плотности строк матрицы B, равной 0,5 и более. Предложенные алгоритмы можно использовать для эффективного планирования распределения ресурсов в GRID-системах в масштабе реального времени при достаточно жестких ограничениях на время решения задач, если допустимое время планирования находится в диапазоне от 5 до 100 мс.

Індекс рубрикатора НБУВ: В173.112.1

Рубрики:

Комбінаторне програмування

Шифр НБУВ: Ж14163 Пошук видання у каталогах НБУВ 

---

Додаткова інформація про автора(ів) публікації:
(cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)

• Лістровий Сергій Володимирович (1950–2018) (технічні науки)

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"