Максимальное независимое множество

Максимальное независимое множество

Из Википедии, свободной энциклопедии

Перейти к навигации Перейти к поиску

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

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

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

Например, на графике {\ displaystyleP _{3}}, путь с тремя вершинами {\ displaystylea }, {\ displaystyleb } и {\ displaystylec }, и два края {\ displaystyleab } и {\ displaystylebc }, наборы {\ displaystyle \{ b \}} и {\ displaystyle \{ a, c \}} оба максимально независимы. Набор {\ displaystyle \{ a \}} является независимым, но не является максимально независимым, поскольку является подмножеством большего независимого множества {\ displaystyle \{ a, c \}}. В этом же графе максимальные клики — это множества. {\ displaystyle \{ a, b \}} и {\ displaystyle \{ b, c \}}.

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

Две лучшие {\ displaystyleP _{3}} графы являются максимальными независимыми множествами, в то время как два нижних являются независимыми множествами, но не максимальными. Максимальное независимое множество представлено в левом верхнем углу.

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

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

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

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

Содержание

• 1Определение
• 2Связанные наборы вершин
• 3Характеристики семейства графов
• 4Ограниченное число наборов
• 5Нахождение единого максимального независимого множества
• 5.1Последовательный алгоритм
• 5.2Параллельный алгоритм случайного выбора [Алгоритм Луби]
• 5.3Параллельный алгоритм со случайным приоритетом
• 5.4Алгоритм параллели случайной перестановки [Алгоритм Блеллоха]
• 6Перечисление всех максимальных независимых множеств
• 7Распараллеливание нахождения максимальных независимых множеств
• 7.1История
• 7.2Класс сложности
• 7.3Связь и обмен данными
• 8Примечания
• 9Ссылки

Определение[ править ]

Для графика {\ displaystyleG =(V; E)}, независимый набор {\ displaystyleS } — максимальное независимое множество, если для {\ displaystylev \ inV }, верно одно из следующих условий: ^[2]

1. {\displaystyle v\in S}

2. {\displaystyle N(v)\cap S\neq \emptyset } где {\displaystyle N(v)} обозначает соседей {\displaystyle v}

Вышесказанное может быть переформлировано как вершина, либо принадлежащая независимому множеству, либо имеет по меньшей мере одну соседнюю вершину, которая принадлежит независимому множеству. В результате каждое ребро графа имеет по крайней мере одну конечную точку, отсутствуют в {\ displaystyleS }. Однако неверно, что каждое ребро графа имеет по крайней мере одну или даже одну конечную точку в {\ displaystyleS }

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

Связанные наборы вершин[ править ]

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

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

Слева — максимальное независимое множество. Середина – это клика, {\ displaystyleK _{3}}, на графике дополнения. Справа — вершинная крышка на максимально независимом множестве дополнения.

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

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

Характеристики семейства графов[ править ]

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

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

Ограничивая количество наборов[ править ]

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

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

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

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

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

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

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

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

Вернуть I.

Вернуть I.

Вернуть I.

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

АНАЛИЗ:

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

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

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

Вернуть I.

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

Вернуть I.

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

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

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

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

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

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

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

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

История [ править ]

Задача максимального независимого множества первоначально считалась нетривиальной для распараллелива в связи с тем, что лексикографическое максимальное независимое множество оказалось P -полным; однако было показано, что детерминированное параллельное решение может быть дано с помощью {\ displaystyleNC ^{1}} уменьшение либо от максимальной установленной упаковки, либо от задачи максимального соответствия, либо на {\ displaystyleNC ^{2}} сокращение от 2-х удовлетворительной задачи. ^{[16] [17]} Как правило, структура приведенного алгоритма следует другим алгоритмам параллельных графов — то есть они подразделяют граф на более мелкие локальные задачи, которые решаемы параллельно путем запуска идентичного алгоритма.

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

Класс сложности [ править ]

В 1984 году Карп и др. показали, что детерминированное параллельное решение на PRAM к максимальному независимому множеству принадлежит к зоопарку сложности класса Ника {\ displaystyleNC _{4}}. ^[18] То есть их алгоритм находит максимальное независимое множество в {\ displaystyleO (\ log ^{4} n)} использование {\ displaystyleO ((n /\ logn)^{3})} где {\ displaystylen } — размер набора вершин. В том же документе рандомизированное параллельное решение было также предоставлено со временем выполнения {\ displaystyleO (\ log ^{4} n)} использование {\ displaystyleO (n ^{2})} Процессоры. Вскоре после этого Luby и Alonetal. независимо друг от друга улучшили этот результат, в результате чего задача максимального независимого множества в область {\ displaystyleNC _{2}} с {\ displaystyleO (\ log ^{2} n)} среда выполнения с использованием {\ displaystyleO (mn ^{2})} процессоры, где {\ displaystylem } — число рёбер на графике. ^{[17] [8] [19]} Чтобы показать, что их алгоритм находится в {\ displaystyleNC _{2}}, они изначально представили рандомизированный алгоритм, который использует {\ displaystyleO (m)} процессоры, но могут быть деслучайными с дополнительным {\ displaystyleO (n ^{2})} Процессоры. Сегодня остается открытым вопрос о том, находится ли задача максимально независимого множества в {\ displaystyleNC _{1}}.

Связь и обмен данными [ править ]

Распределенные алгоритмы максимального независимого множества находятся под сильным влиянием алгоритмов модели PRAM. Оригинальная работа LubyandAlonetal. привела к нескольким распределенным алгоритмам. ^{[20] [21] [22] [19]} С точки зрения обмена битами, эти алгоритмы имели нижнюю границу размера сообщения на раунд {\ displaystyleO (\ logn)} бит и потребует дополнительных характеристик графа. Например, необходимо знать размер графа или запрашивать максимальную степень соседних вершин для данной вершины. В 2010 году M é tivieretal. уменьшили требуемый размер сообщения на раунд до {\ displaystyleO (1)}, что является оптимальным и снимает необходимость в каких-либо дополнительных знаниях графа. ^[23]

Примечания[ править ]

1. ^ Erd ő s (1966) показывает, что число различных размеров MISs в n -вершинном графе может быть таким же большим, как n - log n - O (loglog n) и никогда не больше n - log n.

2. ↑ ^b Luby's Algorithm, in: Lecture Notes for Randomized Algorithms, Last Updated by Eric Vigoda on February 2, 2006

3. ^ Weigt & Hartmann (2001).

4. ^ Информационная система о включениях классов графов: максимальные клики неприводимые графы Архивировано 2007-07-09 на WaybackMachine и наследственные максимальные клики неприводимые графы Архивировано 2007-07-08 на WaybackMachine.

5. ^ Бысков (2003). Для получения соответствующих более ранних результатов см. Croitoru (1979) и Eppstein (2003).

6. ^ Тиба и Нишизеки (1985). Тиба и Нишизеки выражают условие наличия O (n) рёбер эквивалентно, в терминах арбористи графов в семействе, быть постоянными.

7. ^ Bisdorff & Marichal (2007); Эйлер (2005); Фюреди (1987).

8. ↑ ^b Luby, M. (1986). "Простой параллельный алгоритм для задачи максимального независимого множества". Журнал SIAM по вычислительной технике. 15 (4): 1036–1053 гг. CiteSeerX 10.1.1.225.5475. doi: 10.1137/0215074.

9. ^ ^{b c} "Принципы распределенных вычислений (лекция 7)" (PDF). ETH Цюрих. Архивировано 21 февраля 2015года. Проверено 21 февраля 2015.

10. ^ Метивье, Ю.; Робсон, Дж. M.; Сахеб-Джахроми, Н.; Земмари А. (2010). "Оптимальный битовой сложности рандомизированный распределенный алгоритм MIS ". Распределенные вычисления. 23 (5–6): 331. doi: 10.1007/ s 00446-010-0121-5. S2CID 36720853.

11. ^ Блеллох, Гай; Файнман, Джереми; Шун, Джулиан (2012). "Жадный последовательный максимальный независимый набор и сопоставление в среднем параллельны". arXiv: 1202.3205 [ cs. ДС ].

12. ^ Эппштейн (2003); Бысков (2003).

13. ^ Эппштейн (2003). Для сопоставления, связанного с широко используемым алгоритмом Брона-Кербоша, см. Tomita, Tanaka & Takahashi (2006).

14. ^ Bomze et al. (1999); Эппштейн (2005); Jennings & Motycková (1992); Johnson, Yannakakis & Papadimitriou (1988); Lawler, Lenstra & Rinnooy Kan (1980); Liang, Dhall & Lakshmivarahan (1991); Makino & Uno (2004); Мишра и Питт (1997); Стикс (2004); Цукияма и др. (1977); Yu & Chen (1993).

15. ^ Makino & Uno (2004); Эппштейн (2005).

16. ^ Кук, Стивен (июнь 1983). "Обзор вычислительной сложности" (PDF). Коммун. СММ. 26 (6): 400–408. doi: 10.1145/358141.358144. S2CID 14323396. Архивировано из оригинала (PDF) 2016-03-04.

17. ^ ^б Барба, Луис (октябрь 2012). "ОБЗОР ЛИТЕРАТУРЫ: Параллельные алгоритмы для задачи максимально независимого множества в графах" (PDF).

18. ^ Карп, Р. M.; Вигдерсон, А. (1984). "Быстрый параллельный алгоритм для задачи максимального независимого множества". 16-й симпозиум ACM по теории вычислений.

19. ^ ^б Алон, Нога; Ласло, Бабай; Алон, Итай (1986). "Быстрый и простой рандомизированный параллельный алгоритм для задачи максимального независимого множества". Журнал алгоритмов. 7 (4): 567–583. DOI: 10.1016/0196-6774(86)90019-2.

20. ^ Пелег, Давид (2000). Распределенные вычисления: подход, учитывающий местные особенности. doi: 10.1137/1.9780898719772. ISBN 978-0-89871-464-7.

21. ^ Линч, Н.А. (1996). "Распределенные алгоритмы". Морган Кауфманн.

22. ^ Ваттенхофер Р. "Глава 4: Максимальное независимое множество" (PDF).

23. ^ Метивье, Ю.; Робсон, Дж. M.; Сахеб-Джахроми, Н.; Земмари А. (2010). "Оптимальный битовой сложности рандомизированный распределенный алгоритм MIS". Распределенные вычисления.

Список литературы[ править ]

• Бисдорф, Р.; Маричал, Ж.-Л. (2007), Подсчет неизоморфных максимальных независимых множеств n -циклического графа, arXiv: math. CO /0701647.
• Бомзе, И. M.; Будинич, М.; Пардалос, П. M.; Пелильо, М. (1999), «Задача максимальной клики», HandbookofCombinatorialOptimization,4, KluwerAcademicPublishers, pp. 1–74, CiteSeerX 10.1.1.48.4074.
• Бысков Ж. M. (2003), «Алгоритмы k -окрашиванияи нахождения максимальных независимых множеств», Труды XIV ежегодного симпозиума ACM - SIAM по дискретным алгоритмам, Soda '03, стр. 456–457, ISBN 9780898715385.
• Тиба, Н.; Нишизеки, Т. (1985), «Алгоритмы арбории и перечисления подграфов», SIAMJournalonComputing, 14 (1): 210–223, doi: 10.1137/0214017, S 2 CID 207051803.
• Croitoru, C. (1979), "On stables in graphs", Proc. Third Coll. Operations Research, Babeş-Bolyai University, Cluj-Napoca, Romania, pp. 55–60.
• Eppstein, D. (2003), "Малые максимальные независимые множества и более быстрая точная раскраска графов" (PDF), Journal of Graph Algorithms and Applications, 7 (2): 131–140, arXiv: cs. DS/0011009, CiteSeerX 10.1.1.342.4049, doi: 10.7155/jgaa.00064.
• Eppstein, D. (2005), "All maximal independent sets and dynamic dominance for sparse graphs", Proc. Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 5, pp. 451–459, arXiv: cs. DS/0407036, doi: 10.1145/1597036.1597042, S2CID 2769046.
• Erdős, P. (1966), "On cliques in graphs", Israel Journal of Mathematics, 4 (4): 233–234, doi: 10.1007/BF02771637, MR 0205874, S2CID 121993028.
• Эйлер, Р. (2005), "Число Фибоначчи графа сетки и новый класс целочисленных последовательностей", Journal of Integer Sequences, 8 (2): 05.2.6, Bibcode: 2005JIntS... 8...26Е.
• F ü redi, Z. (1987), "Число максимальных независимых множеств в связанных графах", JournalofGraphTheory, 11 (4): 463–470, doi: 10.1002/ jgt.3190110403.
• Дженнингс, Э.; Motyckov á, L. (1992), "Распределенный алгоритм нахождения всех максимальных клик в сетевом графе", Proc. Первый латиноамериканский симпозиум по теоретической информатике,Конспекты лекций по информатике, 583, Springer - Verlag, стр. 281–293
• Джонсон, Д. С.; Яннакакис, М.; Пападимитриу, К. Х. (1988), «О генерации всех максимальных независимых множеств», Письма об обработке информации, 27 (3): 119–123, doi: 10.1016/0020-0190(88)90065-8.
• Лоулер, Э. Л. (1976), «Заметка о сложности задачи хроматического числа», InformationProcessingLetters, 5 (3): 66–67, doi: 10.1016/0020-0190(76)90065- X.
• Лоулер, Э. Л.; Ленстра, Дж.К.; RinnooyKan, A. H. G. (1980), «Генерация всех максимальных независимых множеств: NP -твердость и алгоритмы полиномиального времени» (PDF), SIAMJournalonComputing, 9 (3): 558–565, doi: 10.1137/0209042.
• Люн, Ж. Ю.-Т. (1984), «Быстрые алгоритмы генерации всех максимальных независимых множеств интервальных, циркулярно-дуговых и хордальных графов», JournalofAlgorithms, 5: 22–35, doi: 10.1016/0196-6774(84)90037-3.
• Лян, Ю. Д.; Дхолл, С. К.; Лакшмиварахан, С. (1991), «О проблеме нахождения всех независимых множеств максимального веса в интервальных и круговых дуговых графах», Материалы Симпозиума по прикладным вычислениям 1991 года,стр. 465–470, doi: 10.1109/ SOAC.1991.143921
• Макино, К.; Uno, T. (2004), "New algorithms for enumerating all maximal cliques", Proc. Nine Scandinavian Workshop on Algorithm Theory,Lecture Notes in Compute Science, 3111, Springer-Verlag, pp. 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. Tenth Conf. Computational Learning Theory,pp. 211–217, doi: 10.1145/267460.267500, ISBN 978-0-89791-891-6, S2CID 5254186.
• Мун, Дж.У.; Мозер, Л. (1965), «О кликах в графах», Israel Journal of Mathematics, 3: 23–28, doi: 10.1007/BF02760024, MR 0182577, S2CID 9855414.
• Stix, V. (2004), "Finding all maximal cliques in dynamic graphs", Computational Optimization Appl., 27 (2): 173–186, CiteSeerX 10.1.1.497.6424, doi: 10.1023/B:COAP.0000008651.28952.b6, S2CID 17824282
• Томита, Э.; Танака, А.; Такахаши, Х. (2006), «Наихудшая временная сложность для генерации всех максимальных клик и вычислительных экспериментов», TheoreticalComputerScience, 363 (1): 28–42, doi: 10.1016/ j. tcs.2006.06.015.
• Цукияма, С.; Иде, М.; Ариёси, Х.; Shirakawa, I. (1977), "Новый алгоритм генерации всех максимальных независимых множеств", SIAMJournalonComputing, 6 (3): 505–517, doi: 10.1137/0206036.
• Вайгт, Мартин; Hartmann, Alexander K. (2001), "Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture", Phys. Rev. E, 63 (5): 056127, arXiv: cond-mat/0011446, Bibcode: 2001PhRvE.. 63e6127W, doi: 10.1103/PhysRevE.63.056127, PMID 11414981, S2CID 16773685.
• Ю, К.-В.; Чэнь, Г.-Х. (1993), «Генерация всех максимальных независимых множеств в перестановках графов», Internat. Дж. Мат., 47 (1–2): 1–8, дои: 10.1080/00207169308804157.

Категории:

• Объекты теории графов
• Вычислительные задачи в теории графов

Максимальное независимое множество