Эффективность распарралеливания метода Магу получения клик графа

Вид работы: статья | Предмет работы: Прикладная математика | Количество листов: 5

Для простого, неориентированного графа без петель и кратных ребер полный подграф называется кликой, а наибольшая по числу входящих вершин клика максимальной. Иначе говоря, максимальной кликой называется наибольшее из возможных подмножеств вершин графа, где между каждой парой вершин существует ребро [2].

Аннотация. В работе рассматривается задача об определении кликового числа неориентированного графа без петель на n вершинах. Известно, что такая задача является NP — полной. В работе анализируется эффективность распараллеливания метода Магу нахождения максимальной клики графа с точки зрения скорости работы. Приводятся результаты применения метода для различных графов.
Ключевые слова: максимальная клика, NP-полная задача, кликовое число графа.

ПОМОЩЬ С НАУЧНОЙ РАБОТОЙ

Подготовим для Вас работу по стандартам Вузов

Готовая работа с высокой уникальностью по минимальной цене

Срок выполнения от 2 часов

Антиплагиат более 70%

Быстрый заказ работы