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

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

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

Например, в графе , путь с тремя вершинами , , и , и двух краев и , наборов и оба максимально независимы. Набор является независимым, но не максимально независимым, потому что он является подмножеством большего независимого набора . В этом же графе максимальными кликами являются множества и .${\ displaystyle P_ {3}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle ab}$${\ displaystyle bc}$${\ Displaystyle \ {Ь \}}$${\ Displaystyle \ {а, с \}}$${\ Displaystyle \ {а \}}$${\ Displaystyle \ {а, с \}}$${\ Displaystyle \ {а, Ь \}}$${\ displaystyle \ {b, c \}}$

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

Два верхних графика - это максимальные независимые множества, а два нижних - независимые, но не максимальные. Максимальный независимый набор представлен в верхнем левом углу.${\ displaystyle P_ {3}}$

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

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

Два независимых набора для звездного графа показывают, насколько сильно могут быть разные по размеру два максимальных независимых набора (правый - максимальный).${\ displaystyle S_ {8}}$

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

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

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

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

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

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

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

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

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

Слева - максимальное независимое множество. Середина - это клика на дополнении графа. Справа - вершинное покрытие на максимальном независимом дополнении множества.${\displaystyle K_{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), легко найти одну ИСУ, используя следующий алгоритм:

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

Время выполнения - O ( m ), поскольку в худшем случае мы должны проверять все ребра.

O (m), очевидно, является наилучшим временем выполнения для последовательного алгоритма. Но параллельный алгоритм может решить проблему намного быстрее.

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

Следующий алгоритм находит MIS за время O (log n ). ^{[2] [8] [9]}

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

АНАЛИЗ : для каждого узла 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 - количество ребер. Это ограничено .${\displaystyle O(\log(n))}$

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

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

Следующий алгоритм лучше предыдущего тем, что в каждый компонент связности всегда добавляется по крайней мере один новый узел: ^{[10] [9]}

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

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

АНАЛИЗ :

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

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

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

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

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

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

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

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

• Если на шаге i мы выбираем , где D - максимальная степень узла в графе, тогда WHP все узлы, оставшиеся после шага i, имеют степень не выше . Таким образом, после шагов log ( D ) все оставшиеся узлы имеют степень 0 (поскольку D < n ) и могут быть удалены за один шаг.${\displaystyle \delta =2^{i}\log {(n)}/D}$${\displaystyle D/2^{i}}$
• Если на любом этапе степень каждого узла не превосходит d , и мы выбираем (для любой константы C ), то WHP самый длинный путь в ориентированном графе, определяемый фиксированным порядком, имеет длину . Следовательно, полностью параллельный алгоритм занимает максимум шагов (поскольку самый длинный путь - это наихудший предел количества шагов в этом алгоритме).${\displaystyle \delta =C\log {(n)}/d}$${\displaystyle O(\log(n))}$${\displaystyle O(\log(n))}$
• Объединение этих двух фактов дает, что, если мы выберем , то WHP время выполнения частично параллельного алгоритма равно .${\displaystyle \delta =2^{i}\log {(n)}/D}$${\displaystyle O(\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-полным ; однако было показано, что детерминированное параллельное решение может быть дано сокращением либо от максимальной упаковки набора, либо от задачи максимального согласования, либо путем сокращения от проблемы 2-выполнимости . ^{[16] [17]} Как правило, структура данного алгоритма следует другим алгоритмам с параллельным графом - то есть они подразделяют граф на более мелкие локальные задачи, которые решаются параллельно, выполняя идентичный алгоритм.${\displaystyle NC^{1}}$${\displaystyle NC^{2}}$

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

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

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

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

Алгоритмы распределенного максимального независимого набора сильно зависят от алгоритмов модели PRAM. Оригинальная работа Luby и Alon et al. привело к созданию нескольких распределенных алгоритмов. ^{[20] [21] [22] [19]} С точки зрения обмена битами, эти алгоритмы имели нижнюю границу размера сообщения на раунд битов и потребовали дополнительных характеристик графа. Например, необходимо знать размер графа или можно запросить максимальную степень соседних вершин для данной вершины. В 2010 году Métivier et al. уменьшил требуемый размер сообщения за раунд до , что является оптимальным, и устранил необходимость в дополнительных знаниях графа. ^[23]${\displaystyle O(\log n)}$${\displaystyle O(1)}$

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

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