Максимально независимый набор

Эта статья посвящена комбинаторным аспектам максимальных независимых множеств вершин в графе. Более строгое понятие с похожим названием см. в разделе Максимальный независимый набор . Другие аспекты независимых множеств вершин в теории графов см. в разделе Независимое множество (теория графов) . Чтобы узнать о других видах независимых множеств, см. Независимый набор (значения) .

Граф куба имеет шесть различных независимых множеств (два из них максимальные), показанных красными вершинами.

В теории графов максимальное независимое множество ( MIS ) или максимальное стабильное множество — это независимое множество , которое не является подмножеством какого-либо другого независимого множества. Другими словами, вне независимого множества не существует вершины , которая могла бы к нему присоединиться, поскольку она максимальна по свойству независимого множества.

Например, в графе P3 _, , пути с тремя вершинами a , b и c и двумя ребрами ab и bc множества { b } и { a , c } максимально независимы. Набор { a } независим, но не является максимально независимым, поскольку он является подмножеством большего независимого набора { a , c }. В этом же графе максимальные клики — это множества { a , b } и { b , c }.

MIS также является доминирующим множеством в графе, и каждое независимое доминирующее множество должно быть максимально независимым, поэтому MIS также называют независимыми доминирующими множествами .

Два верхних графа P ₃ представляют собой максимальные независимые множества, а два нижних — независимые множества, но не максимальные. Максимальный независимый набор представлен вверху слева.

Граф может иметь множество MIS самых разных размеров; Самый большой или, возможно, несколько одинаково больших МИС графа называется максимальным независимым множеством . Графы, в которых все максимальные независимые множества имеют одинаковый размер, называются хорошо покрытыми графами .

Фраза «максимальный независимый набор» также используется для описания максимальных подмножеств независимых элементов в математических структурах, отличных от графов, и, в частности, в векторных пространствах и матроидах .

Два независимых набора для звездного графа S8 _{показывают ,} насколько сильно могут различаться по размеру два максимальных независимых набора (правый — максимальный).

две алгоритмические проблемы С MIS связаны : поиск одной MIS в заданном графе и составление списка всех MIS в данном графе .

Определение

Для графика $G=(V,E)$, независимое множество $S$ является максимальным независимым множеством, если для $v\in V$, верно одно из следующих утверждений:

1. $v\in S$
2. $N(v)\cap S\neq \emptyset$ где $N(v)$ обозначает соседей $v$

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

Обратите внимание, что любой сосед вершины в независимом множестве $S$ не может быть в $S$ потому что эти вершины не пересекаются по определению независимого множества.

Связанные наборы вершин

Если S — максимальное независимое множество в некотором графе, это максимальная клика или максимально полный подграф в дополнительном графе . Максимальная клика — это набор вершин, который индуцирует и полный подграф который не является подмножеством вершин какого-либо большего полного подграфа. То есть это множество S такое, что каждая пара вершин в S соединена ребром, и в каждой вершине, не входящей в S, отсутствует ребро хотя бы с одной вершиной в S . Граф может иметь множество максимальных клик разного размера; нахождение наибольшего из них является задачей максимальной клики .

Некоторые авторы включают максимальность в определение клики и называют максимальные клики просто кликами.

Слева — максимальное независимое множество. Середина - это клика, $K_{3}$, на графе дополнения. Right — вершинное покрытие на максимальном независимом дополнении множества.

Дополнение минимальное максимального независимого множества, т. е. множество вершин, не принадлежащих независимому множеству, образует вершинное покрытие . То есть дополнение представляет собой вершинное покрытие , набор вершин, включающий хотя бы одну конечную точку каждого ребра, и минимальное в том смысле, что ни одну из его вершин нельзя удалить, сохраняя при этом свойство, что оно является покрытием. Минимальные вершинные покрытия изучались в статистической механике в связи с моделью решетчатого газа твердых сфер , математической абстракцией переходов жидкость-твердое состояние.

Каждое максимальное независимое множество является доминирующим множеством , набором вершин, в котором каждая вершина графа либо принадлежит множеству, либо смежна с ним. Множество вершин является максимальным независимым множеством тогда и только тогда, когда оно является независимым доминирующим множеством.

Характеристики семейства графов

Некоторые семейства графов также были охарактеризованы с точки зрения их максимальных клик или максимальных независимых множеств. Примеры включают неприводимые графы максимальной клики и наследственные неприводимые графы максимальной клики. Граф называется неприводимым по максимальной клике , если каждая максимальная клика имеет ребро, не принадлежащее никакой другой максимальной клике, и наследственной неприводимой по максимальной клике, если то же свойство справедливо для каждого индуцированного подграфа. Наследственные неприводимые графы максимальной клики включают графы без треугольников , двудольные графы и интервальные графы .

Кографы можно охарактеризовать как графы, в которых каждая максимальная клика пересекает каждое максимальное независимое множество и в которых то же свойство справедливо во всех индуцированных подграфах.

Ограничение количества наборов

Мун и Мозер (1965) показали, что любой граф с n вершинами имеет не более 3 ^{н /3} максимальные клики. Кроме того, любой граф с n вершинами также имеет не более 3 ^{н /3} максимальные независимые множества. Граф, в котором ровно 3 ^{н /3} Максимальные независимые множества построить легко: просто возьмите непересекающееся объединение n /3 графов треугольников . Любое максимальное независимое множество в этом графе образуется выбором одной вершины из каждого треугольника. Дополнительный граф, в котором ровно 3 ^{н /3} максимальные клики — это особый тип графа Турана ; из-за их связи с Муном и границей Мозера эти графики также иногда называют графами Луны-Мозера. Более жесткие границы возможны, если ограничить размер максимальных независимых множеств: количество максимальных независимых множеств размера k в любом n -вершинном графе не превышает

$\lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.$

Графы, достигающие этой границы, снова являются графами Турана.

Однако некоторые семейства графов могут иметь гораздо более строгие ограничения на количество максимальных независимых множеств или максимальных клик. Если все n -вершинные графы в семействе графов имеют O( n ) ребер и если каждый подграф графа в семействе также принадлежит этому семейству, то каждый граф в семействе может иметь не более O( n ) максимальных клик , все из которых имеют размер O(1). Например, эти условия верны для планарных графов : каждый планарный граф с n -вершинами имеет не более 3 n − 6 ребер, а подграф планарного графа всегда планарен, из чего следует, что каждый планарный граф имеет O( n ) максимальные клики (размером не более четырех). Графы интервалов и хордальные графы также имеют не более n максимальных клик, хотя они не всегда являются разреженными графами .

Число максимальных независимых множеств в n- вершинных графах циклов определяется числами Перрена , а количество максимальных независимых множеств в n -вершинных графах путей определяется последовательностью Падована . Следовательно, оба числа пропорциональны степеням 1,324718, коэффициенту пластичности .

Нахождение единственного максимального независимого набора

Последовательный алгоритм

Учитывая граф G(V,E), легко найти одну MIS, используя следующий алгоритм:

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Выберите узел vεV;
   • Добавьте v к множеству I;
   • Удалите из V узел v и всех его соседей.
3. Вернись И.

Параллельный алгоритм случайного выбора [алгоритм Луби]

Следующий алгоритм находит MIS за время O(log n ).

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Выберите случайный набор вершин S ⊆ V, выбрав каждую вершину v независимо с вероятностью 1/(2d(v)), где d — степень v (количество соседей v).
   • Для каждого ребра в E, если обе его конечные точки находятся в случайном множестве S, удалите из S ту конечную точку, степень которой ниже (т. е. имеет меньше соседей). Разрывайте связи произвольно, например, используя лексикографический порядок имен вершин.
   • Добавьте набор S к I.
   • Удалите из V множество S и всех соседей узлов из S.
3. Вернись И.

АНАЛИЗ : Для каждого узла v разделите его соседей на младших соседей (чей уровень ниже, чем степень v) и более высоких соседей (чей уровень выше, чем степень v), разрывая связи, как в алгоритме.

Назовите узел v плохим , если более 2/3 его соседей являются старшими соседями. Назовите ребро плохим, если обе его конечные точки плохие; в противном случае край хороший .

• По крайней мере, 1/2 всех ребер всегда хорошие. ДОКАЗАТЕЛЬСТВО: постройте направленную версию G, направляя каждое ребро к узлу с более высокой степенью (произвольно разрывая связи). Таким образом, для каждого плохого узла количество исходящих ребер более чем в 2 раза превышает количество входящих ребер. Таким образом, каждому плохому ребру, входящему в узел v, можно сопоставить отдельный набор из двух ребер, выходящих из узла v. Следовательно, общее количество ребер как минимум в 2 раза превышает количество плохих ребер.
• Для каждого хорошего узла u вероятность того, что сосед u будет выбран для S, равна как минимум некоторой положительной константе. ДОКАЗАТЕЛЬСТВО: вероятность того, что для S не выбран ни один сосед u, не превышает вероятности того, что ни один из нижних соседей u не выбран. Для каждого нижнего соседа v вероятность того, что он не выбран, равна (1-1/2d(v)), что не более (1-1/2d(u)) (поскольку d(u)>d(v )). Число таких соседей не меньше d(u)/3, поскольку u хорошее. Следовательно, вероятность того, что ни один нижний сосед не будет выбран, не превышает 1-exp(-1/6).
• Для каждого узла u, выбранного в S, вероятность того, что u будет удален из S, составляет не более 1/2. ДОКАЗАТЕЛЬСТВО: эта вероятность не превышает вероятности того, что старший сосед u будет выбран для S. Для каждого старшего соседа v вероятность того, что он будет выбран, составляет не более 1/2d(v), что составляет не более 1/ 2d(u) (поскольку d(v)>d(u)). По объединению вероятность того, что ни один старший сосед не будет выбран, не превышает d(u)/2d(u) = 1/2.
• Следовательно, для каждого хорошего узла u вероятность того, что сосед u будет выбран для S и останется в S, является некоторой положительной константой. Следовательно, вероятность того, что u будет удалена на каждом этапе, является, по крайней мере, положительной константой.
• Следовательно, для каждого хорошего ребра e вероятность того, что e будет удалена на каждом шаге, является как минимум положительной константой. Таким образом, количество хороших ребер с каждым шагом уменьшается как минимум в постоянный коэффициент.
• Поскольку по крайней мере половина ребер хорошие, общее количество ребер также уменьшается в постоянный коэффициент на каждом шаге.
• Следовательно, количество шагов равно O(log m ), где m — количество ребер. Это ограничено $O(\log(n))$.

Граф наихудшего случая, в котором среднее количество шагов равно $\Theta (\log(n))$, представляет собой граф, состоящий из n /2 связных компонентов, каждый из которых имеет 2 узла. Степень всех узлов равна 1, поэтому каждый узел выбирается с вероятностью 1/2, а с вероятностью 1/4 оба узла в компоненте не выбираются. Следовательно, количество узлов уменьшается в 4 раза на каждом шаге, а ожидаемое количество шагов равно $\log _{4}(n)$.

Параллельный алгоритм со случайным приоритетом

Следующий алгоритм лучше предыдущего тем, что в каждом связном компоненте всегда добавляется хотя бы один новый узел:

1. Инициализируйте I пустым набором.
2. Хотя V не пуст, каждый узел v выполняет следующие действия:
   • Выбирает случайное число r(v) в [0,1] и отправляет его соседям;
   • Если r(v) меньше числа всех соседей v, то v вставляет себя в I, удаляется из V и сообщает об этом своим соседям;
   • Если v услышал, что один из его соседей проник в I, то v удаляется из V.
3. Вернись И.

Обратите внимание, что на каждом шаге узел с наименьшим номером в каждом компоненте связности всегда входит в I, поэтому некоторый прогресс всегда имеется. В частности, в худшем случае предыдущего алгоритма ( n /2 связных компонента по 2 узла в каждом) MIS будет найден за один шаг.

АНАЛИЗ :

• Узел $v$ имеет вероятность как минимум ${\frac {1}{d(v)+d(w)}}$ быть удалены. ДОКАЗАТЕЛЬСТВО: для каждого ребра, соединяющего пару узлов $(v,w)$, замените его двумя направленными ребрами, одним из $(v,w)$ и другой $(w,v)$. Обратите внимание, что $|E|$ теперь в два раза больше. Для каждой пары направленных ребер $(v,w)$, определите два события: $(v\rightarrow w)$ и $(w\rightarrow v)$, $v$ превентивно удаляет $w$ и $w$ превентивно удаляет $v$, соответственно. Событие $(v\rightarrow w)$ происходит, когда $r(v)<r(w)$ и $r(v)<r(x)$, где $w$ является соседом $v$ и $x$ сосед $w$. Напомним, что каждому узлу присваивается случайное число в том же диапазоне [0, 1]. В простом примере с двумя непересекающимися узлами каждый имеет вероятность ${\frac {1}{2}}$ быть самым маленьким. Если есть три непересекающихся узла, каждый имеет вероятность ${\frac {1}{3}}$ быть самым маленьким. В случае $v$, оно имеет вероятность как минимум ${\frac {1}{d(v)+d(w)}}$ быть наименьшим, потому что возможно, что сосед $v$ также является соседом $w$, поэтому узел учитывается дважды. Используя ту же логику, событие $(w\rightarrow v)$ также имеет вероятность как минимум ${\frac {1}{d(w)+d(v)}}$ быть удалены.
• Когда события $(v\rightarrow w)$ и $(w\rightarrow v)$ происходят, они удаляют $d(w)$ и $d(v)$ направленные исходящие ребра соответственно. ДОКАЗАТЕЛЬСТВО: В случае $(v\rightarrow w)$, когда $v$ удаляется, все соседние узлы $w$ также удаляются. Количество исходящих направленных ребер из $w$ удалено $d(w)$. По той же логике $(w\rightarrow v)$ удаляет $d(v)$ направленные исходящие ребра.
• На каждой итерации шага 2 ожидаемо удаляется половина ребер. ДОКАЗАТЕЛЬСТВО: Если событие $(v\rightarrow w)$ случается, тогда все соседи $w$ удаляются; следовательно, ожидаемое количество ребер, удаленных из-за этого события, не менее ${\frac {d(w)}{d(v)+d(w)}}$. То же самое верно и для обратного события $(w\rightarrow v)$, т.е. ожидаемое количество удаленных ребер не менее ${\frac {d(v)}{d(w)+d(v)}}$. Следовательно, для каждого ненаправленного ребра $(w,v)$, ожидаемое количество ребер, удаленных из-за того, что один из этих узлов имеет наименьшее значение, равно ${\frac {d(w)+d(v)}{d(w)+d(v)}}=1$. Суммируя по всем ребрам, $\sum _{{v,w}\in E}1=|E|$, дает ожидаемое количество $|E|$ ребра удаляются на каждом шаге, но каждое ребро учитывается дважды (по одному на каждое направление), что дает ${\frac {|E|}{2}}$ края удаляются в ожидании каждого шага.
• Следовательно, ожидаемое время работы алгоритма равно $3\log _{4/3}(m)+1$ который $O(\log(n))$.

Параллельный алгоритм со случайными перестановками [алгоритм Блеллоха]

Вместо рандомизации на каждом этапе можно выполнить рандомизацию один раз, в начале алгоритма, зафиксировав случайный порядок узлов. Учитывая этот фиксированный порядок, следующий параллельный алгоритм достигает точно такого же MIS, что и алгоритм #Sequential (т. е. результат является детерминированным):

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Пусть W — множество вершин в V, не имеющих предыдущих соседей (на основе фиксированного порядка);
   • Добавьте W к I;
   • Удалите из V узлы множества W и всех их соседей.
3. Вернись И.

Между полностью последовательными и полностью параллельными алгоритмами существует континуум частично последовательных и частично параллельных алгоритмов. Учитывая фиксированный порядок узлов и коэффициент δε(0,1), следующий алгоритм возвращает ту же MIS:

1. Инициализируйте I пустым набором.
2. Пока V не пусто:
   • Выберите коэффициент δε(0,1].
   • Пусть P — множество δ n узлов, которые стоят первыми в фиксированном порядке.
   • Пусть W — MIS на P, использующая полностью параллельный алгоритм.
   • Добавьте W к I;
   • Удалите из V все узлы префикса P и всех соседей узлов множества W.
3. Вернись И.

Установка δ=1/ n дает полностью последовательный алгоритм; установка δ=1 дает полностью параллельный алгоритм.

АНАЛИЗ : При правильном выборе параметра δ в частично параллельном алгоритме можно гарантировать, что он завершится не более чем после log(n) вызовов полностью параллельного алгоритма, а количество шагов в каждом вызове будет не более log. (н). Следовательно, общее время работы частично параллельного алгоритма равно $O(\log ^{2}(n))$. Следовательно, время работы полностью параллельного алгоритма также не превышает $O(\log ^{2}(n))$. Основными этапами доказательства являются:

• Если на шаге i мы выберем $\delta =2^{i}\log {(n)}/D$, где D — максимальная степень узла в графе, тогда WHP все узлы, оставшиеся после шага i, имеют степень не более $D/2^{i}$. Таким образом, после шагов log( D ) все оставшиеся узлы имеют степень 0 (поскольку D < n ) и могут быть удалены за один шаг.
• Если на любом шаге степень каждого узла не превышает d и мы выбираем $\delta =C\log {(n)}/d$ (для любой константы C ), то WHP самый длинный путь в ориентированном графе, определяемом фиксированным порядком, имеет длину $O(\log(n))$. Следовательно, полностью параллельный алгоритм занимает не более $O(\log(n))$ шагов (поскольку самый длинный путь является наихудшим ограничением количества шагов в этом алгоритме).
• Объединение этих двух фактов дает то, что, если мы выберем $\delta =2^{i}\log {(n)}/D$, то WHP время выполнения частично параллельного алгоритма равно $O(\log(D)\log(n))=O(\log ^{2}(n))$.

Перечисление всех максимальных независимых множеств

Дополнительная информация: Проблема клики § Список всех максимальных клик.

Алгоритм перечисления всех максимальных независимых множеств или максимальных клик в графе может использоваться как подпрограмма для решения многих NP-полных задач с графами. Совершенно очевидно, что решения проблемы максимального независимого множества, проблемы максимальной клики и минимальной независимой доминирующей проблемы должны быть максимальными независимыми множествами или максимальными кликами и могут быть найдены с помощью алгоритма, который перечисляет все максимальные независимые множества или максимальные клики и сохраняет те, которые имеют самый большой или самый маленький размер. Аналогично минимальное вершинное покрытие можно найти как дополнение к одному из максимальных независимых множеств. Лоулер (1976) заметил, что перечисление максимальных независимых множеств также можно использовать для поиска 3-раскрасок графов: граф может быть 3-цветным тогда и только тогда, когда дополнение одного из его максимальных независимых множеств двудольно . Он использовал этот подход не только для 3-раскраски, но и как часть более общего алгоритма раскраски графов, и с тех пор подобные подходы к раскраске графов были усовершенствованы другими авторами. Другие более сложные проблемы также можно смоделировать как поиск клики или независимого множества определенного типа. Это мотивирует алгоритмическую проблему эффективного перечисления всех максимальных независимых множеств (или, что то же самое, всех максимальных клик).

Легко перевернуть доказательство Муна и тройки Мозера. ^{н /3} ограниченное число максимальных независимых множеств, в алгоритм, который перечисляет все такие множества за время O(3 ^{н /3} ). Для графов, которые имеют максимально возможное количество максимальных независимых наборов, этот алгоритм требует постоянного времени для каждого выходного набора. Однако алгоритм с такой привязкой по времени может оказаться крайне неэффективным для графов с более ограниченным числом независимых наборов. По этой причине многие исследователи изучали алгоритмы, которые перечисляют все максимальные независимые множества за полиномиальное время для каждого выходного набора. Время на максимальный независимый набор пропорционально времени умножения матриц в плотных графах или быстрее в различных классах разреженных графов.

Подсчет максимальных независимых множеств

Проблема подсчета, связанная с максимальными независимыми множествами, исследовалась в теории сложности вычислений . Задача состоит в том, сколько максимальных независимых множеств содержит неориентированный граф. Эта проблема становится #P -сложной уже тогда, когда входные данные ограничены двудольным графом .

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

Распараллеливание поиска максимальных независимых множеств

История

Первоначально считалось, что проблема максимального независимого множества нетривиальна для распараллеливания из -за того, что лексикографическое максимальное независимое множество оказалось P-полным ; однако было показано, что детерминированное параллельное решение может быть дано с помощью $NC^{1}$ сокращение либо от упаковки максимального множества , либо от задачи максимального сопоставления , либо с помощью $NC^{2}$ редукция из проблемы 2-выполнимости . Обычно структура приведенного алгоритма соответствует другим алгоритмам параллельных графов, то есть они подразделяют граф на более мелкие локальные задачи, которые можно решить параллельно, запустив идентичный алгоритм.

Первоначальные исследования проблемы максимального независимого множества начались с модели PRAM и с тех пор расширились, чтобы дать результаты для распределенных алгоритмов на компьютерных кластерах . Многие проблемы разработки распределенных параллельных алгоритмов применимы в равной степени и к проблеме максимального независимого множества. В частности, поиск алгоритма, который демонстрирует эффективное время выполнения и оптимален при передаче данных для разделения графа и объединения независимого набора.

Класс сложности

Это было показано в 1984 году Карпом и др. что детерминированное параллельное решение на PRAM для максимального независимого множества принадлежало зоопарку классов Ника сложности $NC_{4}$. То есть их алгоритм находит максимальное независимое множество в $O(\log ^{4}n)$ с использованием $O((n/\log n)^{3})$, где $n$ — размер набора вершин. В той же статье также было предоставлено рандомизированное параллельное решение со временем выполнения $O(\log ^{4}n)$ с использованием $O(n^{2})$ процессоры. Вскоре после этого Луби и Алон и др. независимо улучшили этот результат, переведя задачу о максимальном независимом множестве в область $NC_{2}$ с $O(\log ^{2}n)$ время выполнения с использованием $O(mn^{2})$ процессоры, где $m$ — количество ребер в графе. Чтобы показать, что их алгоритм работает $NC_{2}$, они изначально представили рандомизированный алгоритм, который использует $O(m)$ процессоры, но могут быть дерандомизированы с помощью дополнительного $O(n^{2})$ процессоры. Сегодня остается открытым вопрос, существует ли проблема максимального независимого множества. $NC_{1}$.

Связь и обмен данными

Алгоритмы распределенного максимального независимого множества находятся под сильным влиянием алгоритмов модели PRAM. Оригинальная работа Луби и Алона и др. привело к созданию нескольких распределенных алгоритмов. С точки зрения обмена битами эти алгоритмы имели нижнюю границу размера сообщения за раунд. $O(\log n)$ бит и потребует дополнительных характеристик графа. Например, необходимо знать размер графа или можно запросить максимальную степень соседних вершин для данной вершины. В 2010 году Метивье и др. уменьшен требуемый размер сообщения за раунд до $O(1)$, что является оптимальным и устраняет необходимость в каких-либо дополнительных знаниях графов.

Ссылки

• Бисдорф, Раймонд; Маришаль, Жан-Люк (2008), «Подсчет неизоморфных максимальных независимых множеств графа n -циклов» , Журнал целочисленных последовательностей , 11 : 08.5.7, arXiv : math.CO/0701647 .
• Бомзе, ИМ; Будинич, М.; Пардалос, премьер-министр; Пелилло, М. (1999), «Проблема максимальной клики», Справочник по комбинаторной оптимизации , том. 4, Kluwer Academic Publishers, стр. 1–74, CiteSeerX   10.1.1.48.4074 .
• Бысков, Дж. М. (2003), «Алгоритмы k -раскраски и поиска максимальных независимых множеств», Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Soda '03, стр. 456–457, ISBN  9780898715385 .
• Чиба, Н.; Нишизеки, Т. (1985), «Древовидность и алгоритмы перечисления подграфов», SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 , S2CID   207051803 .
• Кроитору, К. (1979), «О конюшнях в графах», Proc. Третий Колл. Исследование операций , Университет Бабеш-Бойяи , Клуж-Напока, Румыния, стр. 55–60 .
• Эппштейн, Д. (2003), «Малые максимальные независимые множества и более быстрая точная раскраска графов» (PDF) , Журнал графовых алгоритмов и приложений , 7 (2): 131–140, arXiv : cs.DS/0011009 , CiteSeerX   10.1. 1.342.4049 , номер домена : 10.7155/jgaa.00064 .
• Эппштейн, Д. (2005), «Все максимальные независимые множества и динамическое доминирование для разреженных графов», Proc. Шестнадцатый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , том. 5, стр. 451–459, arXiv : cs.DS/0407036 , doi : 10.1145/1597036.1597042 , S2CID   2769046 .
• Эрдеш, П. (1966), «О кликах в графах», Израильский журнал математики , 4 (4): 233–234, doi : 10.1007/BF02771637 , MR   0205874 , S2CID   121993028 .
• Эйлер, Р. (2005), «Число Фибоначчи сеточного графа и новый класс целочисленных последовательностей», Журнал целочисленных последовательностей , 8 (2): 05.2.6, Bibcode : 2005JIntS...8...26E .
• Фюреди, З. (1987), «Число максимальных независимых множеств в связных графах», Journal of Graph Theory , 11 (4): 463–470, doi : 10.1002/jgt.3190110403 .
• Дженнингс, Э.; Мотычкова, Л. (1992), "Распределенный алгоритм поиска всех максимальных клик в сетевом графе", Proc. Первый латиноамериканский симпозиум по теоретической информатике , Конспекты лекций по информатике, том. 583, Springer-Verlag, стр. 281–293.
• Джонсон, Д.С .; Яннакакис, М. ; Пападимитриу, CH (1988), «О создании всех максимальных независимых наборов», Information Processing Letters , 27 (3): 119–123, doi : 10.1016/0020-0190(88)90065-8 .
• Лоулер, Э.Л. (1976), «Заметка о сложности проблемы хроматических чисел», Information Processing Letters , 5 (3): 66–67, doi : 10.1016/0020-0190(76)90065-X .
• Лоулер, Эл . ; Ленстра, JK ; Риннуй Кан, AHG (1980), «Генерация всех максимальных независимых множеств: алгоритмы NP-трудности и полиномиального времени» (PDF) , SIAM Journal on Computing , 9 (3): 558–565, doi : 10.1137/0209042 , S2CID   29527771 .
• Люнг, JY-T. (1984), «Быстрые алгоритмы для генерации всех максимальных независимых наборов интервальных, дуговых и хордальных графов», Journal of Algorithms , 5 : 22–35, doi : 10.1016/0196-6774(84)90037-3 .
• Лян, Ю.Д.; Дхалл, СК; Лакшмиварахан, С. (1991), «О проблеме поиска всех независимых множеств с максимальным весом в интервальных и дуговых графах», Труды симпозиума 1991 года по прикладным вычислениям , стр. 465–470, doi : 10.1109/SOAC.1991.143921 , ISBN  0-8186-2136-2 , S2CID   122685841
• Макино, К.; Уно, Т. (2004), «Новые алгоритмы перечисления всех максимальных клик», Proc. Девятый скандинавский семинар по теории алгоритмов , Конспекты лекций по информатике, том. 3111, Springer-Verlag, стр. 260–272, CiteSeerX   10.1.1.138.705 , doi : 10.1007/978-3-540-27810-8_23 , ISBN  978-3-540-22339-9 . ISBN   9783540223399 , 9783540278108 .
• Мишра, Н.; Питт, Л. (1997), "Генерация всех максимальных независимых наборов гиперграфов ограниченной степени", Proc. Десятая конф. Вычислительная теория обучения , стр. 211–217, doi : 10.1145/267460.267500 , ISBN  978-0-89791-891-6 , S2CID   5254186 .
• Мун, Дж.В.; Мозер, Л. (1965), «О кликах в графах», Израильский математический журнал , 3 : 23–28, doi : 10.1007/BF02760024 , MR   0182577 , S2CID   9855414 .
• Стикс, В. (2004), «Нахождение всех максимальных клик в динамических графах», Computational Optimization and Applications , 27 (2): 173–186, CiteSeerX   10.1.1.497.6424 , doi : 10.1023/B:COAP.0000008651.28952.b6 , S2CID   17824282
• Томита, Э.; Танака, А.; Такахаши, Х. (2006), «Временная сложность в наихудшем случае для генерации всех максимальных клик и вычислительных экспериментов», Theoretical Computer Science , 363 (1): 28–42, doi : 10.1016/j.tcs.2006.06.015 .
• Цукияма, С.; Иде, М.; Ариеси, Х.; Сиракава, И. (1977), «Новый алгоритм генерации всех максимальных независимых наборов», SIAM Journal on Computing , 6 (3): 505–517, doi : 10.1137/0206036 .
• Вейгт, Мартин; Хартманн, Александр К. (2001), «Минимальные вершинные покрытия на случайных графах конечной связности: картина решеточного газа твердых сфер», Phys. Ред. E , 63 (5): 056127, arXiv : cond-mat/0011446 , Bibcode : 2001PhRvE..63e6127W , doi : 10.1103/PhysRevE.63.056127 , PMID   11414981 , S2CID   167736 85 .
• Ю, К.-В.; Чен, Г.-Х. (1993), «Сгенерировать все максимальные независимые множества в графах перестановок», Internat. Дж. Компьютер. Математика. , 47 (1–2): 1–8, doi : 10.1080/00207169308804157 .