Алгоритм перечисления клик

9

Я читаю старую статью MC Golumbic о графиках EPT (пересечение ребер в дереве). В статье показано, что число максимальных кликов экземпляра графа EPT является полиномиальным. Он приходит к выводу, что если оракул сообщает, что граф $G$ является графиком EPT, то можно найти максимальную клику с помощью стандартного алгоритма перебора кликов.

Прежде всего, что это за стандартные алгоритмы подсчета кликов? Если их больше одного, можем ли мы сказать, что если число максимальных кликов графа является полиномиальным, то можем ли мы использовать любой из этих алгоритмов перечисления? Или мы должны получить специальный алгоритм из общего алгоритма, который использует некоторые специальные структуры класса графа?

Заранее спасибо.

ds.algorithms graph-algorithms clique Arman
источник

13

Существует несколько чувствительных к выходу алгоритмов для перечисления всех максимальных кликов за полиномиальное время для каждого выхода. Один из самых ранних алгоритмов был разработан Цукияма, Иде, Ариёси и Сиракавой (1977).

Шуджи Цукияма, Микио Иде, Хирому Ариёси, Исао Сиракава: новый алгоритм генерации всех максимальных независимых множеств. SIAM J. Comput. 6 (3): 505-517 (1977)

Это означает, что если вы знаете, что на вашем графике максимально много полиномиальных максимальных кликов, то общее время выполнения их алгоритма будет полиномиальным по входному размеру.

Ёсио Окамото
источник

К сожалению, у меня нет доступа к газете. Но я уверен, что это то, что я ищу, спасибо.

Арман

4

Алгоритм Брон-Кербоша вычисляет все максимальные клики в неориентированном графе (см. Википедия ). Наихудшее время выполнения - O (3 ^{n / 3} ), по-видимому, оно очень быстрое в целом и все еще является самым быстрым из известных алгоритмов для вычисления всех максимальных кликов. Для новой ссылки см документы о В. Стикс и Cazals и Karande .

Фолькер Турау
источник

2

Чтобы получить

O (3^{n / 3})

$O(3^{n/3})$ Связанный, нам нужен небольшой трюк для эффективного выполнения ветвления и связывания в процедуре возврата (из-за Томиты, Танаки и Такахаши). Также хорошо отметить, что границы

3^{n / 3}

$3^{n/3}$ оптимально в худшем случае, так как существует граф с

3^{n / 3}

$3^{n/3}$ максимальный клик (а именно,

K_{3, 3, . . ., 3}

$K_{3,3,...,3}$ ).

Ёсио Окамото

1

Более свежую работу по Брону-Кербошу можно найти в моих статьях arxiv.org/abs/1006.5440 со Strash и Löffler на ISAAC 2010 и arxiv.org/abs/1103.0318 со Strash в SEA 2011. Однако это на самом деле не отвечает на вопрос оригинального автора так как алгоритм не чувствителен к выходу: это может занять экспоненциальное время, даже если максимальные клики полиномиально.

Дэвид Эппштейн

Алгоритм перечисления клик

Ответы: