Розглянуто клас задач, які називають NP-повними. Для задач такого типу не знайдено поліноміальних алгоритмів, проте і не доведено, що таких не існує. Описано методи розв’язання таких задач, наведено приклади їх практичного застосування. Як приклад NP-повної задачі розглянуто “Задачу про кліку”. Наведено новий алгоритм перерахування всіх максимальних клік у розріджених графах за допомогою алгоритму Епстена, Стреша, проаналізовано його виконання на реальних графах. Цим алгоритмом уперше запропоновано практичне рішення перерахунку всіх максимальних великих розріджених графів. Усі інші теоретично швидкі алгоритми для розріджених графів на практиці значно повільніші, ніж алгоритм Томіта й інших. Проте, алгоритмом Томіта й інших використовується матриця суміжності, яка вимагає занадто багато місця для великих розріджених графів. Новий алгоритм запропоновано для швидкого аналізу великих розріджених графів, у яких матриця суміжності не впишеться в робочу пам'ять.

Рассмотрен класс задач, которые называют NP-полными. Для задач такого типа не найдено полиномиальных алгоритмов, однако и не доказано, что таких не существует. Описаны методы решения таких задач, приведены примеры их практического применения. Как пример NP-полной задачи рассмотрена «Задача о клике». Представлен новый алгоритм перечисления всех максимальных клик в разреженных графах с помощью алгоритма Епстена, Стреша, проанализированы его выполнения на реальных графах. Этим алгоритмом впервые предложено практическое решение пересчета всех максимальных больших разреженных графов. Все остальные теоретически быстрые алгоритмы для разреженных графов на практике значительно медленнее, чем алгоритм Томита и других. Однако, алгоритмом Томита и других используется матрица смежности, которая требует слишком много места для больших разреженных графов. Новый алгоритм предложен для быстрого анализа больших разреженных графов, в которых матрица смежности не впишется в рабочую память.

A class of problems, called NP-complete. For this type of problem found polynomial algorithms, but not proven, that these do not exist. It is describes methods for solving such problems, and examples of their practical application. As an example of NP-complete problems considered “problem of the clique”. A new algorithm for enumerating all maximal cliques in sparse graphs using the algorithm Epstena, Stresha analyzed its performance on real graphs. This algorithm first proposed a practical solution to convert all maximal large sparse graphs. All other algorithms for fast theoretically sparse graphs in practice are significantly slower than other algorithm Tomita. However, the algorithm Tomita et al used the adjacency matrix, which requires too much space for large sparse graphs. The new algorithm is proposed for the rapid analysis of large sparse graphs, in which the adjacency matrix does not fit into the working memory.

• Якимович Марія Володимирівна (технічні науки)
• Остапчук Микола Васильович (педагогічні науки)

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