Назад в библиотеку

О сложности советов для задачи онлайн-доминирующего множества

Бёкенхауэр Х.-Й., Хромкович Ю., Круг С., Унгер В.

ETH Zurich, Швейцария; RWTH Aachen University, Германия

Источник: Böckenhauer H.-J., Hromkovic̆ J., Krug S., Unger W. On the advice complexity of the online dominating set problem // Theoretical Computer Science. – 2021. – Vol. 862. – P. 81–96. [Электронный ресурс]. – URL: https://doi.org/10.1016/j.tcs.2021.01.022

Аннотация. Доминирующее множество S графа — это множество вершин, такое что каждая вершина либо принадлежит S, либо имеет соседа в S. Цель задачи доминирующего множества — найти такое множество минимальной мощности. В онлайн-режиме граф раскрывается по одной вершине за раз вместе со всеми рёбрами к ранее раскрытым вершинам.

Сложность советов (advice complexity) — это рамки, позволяющие измерить количество информации, которой не хватает онлайн-алгоритму. Здесь онлайн-алгоритм считывает биты совета с бесконечной двоичной ленты, подготовленной заранее всемогущим оракулом. Сложность совета — это общее число прочитанных советных битов за время вычисления. Помимо выявления того, что делает онлайн-задачу трудной, сложность советов может также использоваться для доказательства нижних оценок на конкурентное отношение, достижимое рандомизированными онлайн-алгоритмами.

В данной работе анализируется сложность советов для задачи онлайн-доминирующего множества. Для общих графов показаны точные верхние и нижние оценки для оптимальности. Затем с использованием результата для c-конкурентности доказывается, что никакой рандомизированный онлайн-алгоритм не может быть лучше чем n1−ε-конкурентным для любого ε > 0. Наконец, анализируется сложность советов для различных классов графов в случае оптимальности.

1. Введение

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

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

В этой модели онлайн-алгоритм имеет доступ к бесконечной двоичной ленте советов во время вычисления. Эта лента готовится заранее всемогущим оракулом. Сложность совета — это число советных битов, которые онлайн-алгоритму необходимо прочитать с ленты во время вычисления, чтобы достичь определённого качества решения. В некотором смысле это отражает объём знаний, которых не хватает онлайн-алгоритму о будущем.

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

Анализируется сложность советов для задачи онлайн-доминирующего множества (DominatingSet) в следующей модели: граф раскрывается по одной вершине за раз; вместе с вершиной раскрываются все рёбра к ранее раскрытым вершинам.

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

2. Предварительные сведения и связанная работа

Кинг и Цзэн [27] показывают с помощью простого примера наихудшего случая, что верхняя оценка конкурентного отношения (отношения между стоимостью полученного решения и стоимостью оптимального решения), равная n − 1 (полученная алгоритмом, который просто принимает каждую ещё не доминированную вершину), является точной. Рассмотрим экземпляр, в котором каждая раскрытая вершина соединяется со всеми ранее раскрытыми, до тех пор пока алгоритм не отвергнет некоторую вершину v. (Если этого не происходит, то входной граф — это полный граф Kn, оптимальное решение которого имеет размер 1. Однако алгоритм принял все n вершин и, следовательно, является лишь n-конкурентным.) Затем все оставшиеся вершины соединяются только с v и, следовательно, должны быть приняты; полученное решение имеет стоимость n − 1. Оптимальное решение, однако, содержит только v и имеет стоимость 1. (Заметим, что авторы также используют другую онлайн-модель, в которой вместе с вершиной раскрываются все её смежные рёбра, в том числе и к ещё не раскрытым вершинам.)

Эйденбенц [20] уточняет эти результаты, исследуя задачу DominatingSet на конкретных классах графов. Он также рассматривает две онлайн-модели. В модели вставки противник раскрывает (вставляет) вершину за один временной шаг. В модели вставки/удаления противник вставляет или удаляет вершину из графа за один временной шаг. В обеих моделях алгоритм не может отклонить ранее принятую вершину. Более того, принятые вершины должны образовывать доминирующее множество на каждом шаге вычислений. Для модели вставки представлены следующие результаты. Для деревьев конкурентное отношение ограничено сверху величиной 3 − ε (для произвольно малого ε > 0) и снизу — 2. Также существуют онлайн-алгоритмы с конкурентным отношением n − 1 для лесов, а также для графов с ограниченной древесной шириной, двудольных, планарных и дисковых графов переменного размера, и эта оценка точна для всех этих классов графов.

Эти модели, в которых доминирующее множество должно поддерживаться на каждом шаге вычислений, также подробно изучались в недавней работе Бояра и др. [13].

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

Определение 1. Онлайн-задача о доминирующем множестве (DominatingSet) — это следующая онлайн-задача минимизации на графе G с n вершинами. На временном шаге i (1 ≤ i ≤ n) раскрывается вершина v из G вместе со всеми рёбрами к ранее раскрытым вершинам. Онлайн-алгоритм для DominatingSet должен немедленно решить, принимать или отклонять v, то есть входит ли v в решение или нет. Цель — получить доминирующее множество минимального размера для G.

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

Определение 2. Онлайн-задача о доминирующем множестве на классе графов C — это задача DominatingSet, ограниченная входными графами из C.

Заметим, что Определение 2 ничего не говорит о графах на промежуточных временных шагах. В частности, они не обязаны принадлежать C. Например, если мы рассматриваем деревья, промежуточные графы не обязаны быть связными.

Эти два определения согласованы в следующем смысле. С одной стороны, мы даём определённую свободу онлайн-алгоритму для DominatingSet: только его окончательный вывод должен быть допустимым решением. С другой стороны, мы также даём определённую свободу противнику: только его конечный вход должен быть допустимым графом.

Теперь формально определим рамки сложности советов, которые мы используем.

Определение 3. Рассмотрим входную последовательность I = (x1, ..., xn). Онлайн-алгоритм A с советами вычисляет выходную последовательность Aφ(I) = (y1, ..., yn), такую что yi вычисляется из φ, x1, ..., xi, где φ — содержимое советской ленты, то есть бесконечная битовая строка. Алгоритм A является c-конкурентным со сложностью совета s(n), если для любого n и любой входной последовательности I длины не более n существует некоторая φ, такая что стоимость(Aφ(I)) ≤ c · стоимость(Opt(I)) + α для некоторой неотрицательной константы α, и за время вычисления A на I было использовано не более первых s(n) битов φ. Если α = 0, то говорят, что A является строго c-конкурентным.

В дальнейшем будем обозначать ℕ := {0, 1, ...} и ℕ≥k := {n ∈ ℕ | n ≥ k} для любого k ∈ ℕ. Кроме того, ℕ+ := ℕ≥1. Бинарный логарифм числа x будем обозначать как log x. Размер графа — это число его вершин.

Отметим, что положительное целое число n можно закодировать на советской ленте саморазделяющимся способом, используя Log n := max{2, ⌈log n⌉ + 2⌈log ⌈log n⌉⌉} советских битов [21], см. также [28].

Перед тем как начать, кратко рассмотрим кодирование n q-арных решений на (бинарной) советской ленте для некоторого q ∈ ℕ≥3. По существу, их можно закодировать таким образом, что количество потраченных впустую советских битов асимптотически стремится к 0. Если n известно заранее, алгоритм просто читает ⌈n log q⌉ советских битов с ленты. Поскольку 2⌈n log q⌉ ≥ qn, каждая возможная последовательность q-арных решений длины n может быть закодирована разной советской строкой на ленте. Более того, легко проверить, что эта оценка точна, то есть ⌈n log q⌉ советских битов необходимо и достаточно.

Если n неизвестно заранее, то первые Log n советских битов кодируют число n саморазделяющимся способом. После прочтения этих битов и, следовательно, знания n, алгоритм действует, как описано выше. Дополнительные советские биты асимптотически несущественны, поскольку limn→∞ (Log n + ⌈n log q⌉) / ⌈n log q⌉ = 1.

Часто мы рассматриваем следующий очень простой жадный алгоритм.

Определение 4. Жадный алгоритм G принимает вновь раскрытую вершину тогда и только тогда, когда она не доминирована уже принятой вершиной.

3. Общие графы и деревья

Жадный алгоритм G отклоняет по крайней мере одну вершину, если граф содержит ребро. В противном случае граф состоит только из изолированных вершин, и G является оптимальным. Более того, известно, что не существует лучшего детерминированного онлайн-алгоритма для DominatingSet на общих графах [27].

Наблюдение 1. Жадный алгоритм G является строго (n − 1)-конкурентным для n ≥ 2, и эта оценка точна для детерминированных онлайн-алгоритмов без советов.

Рассматривая оптимальные алгоритмы, мы получаем следующие почти совпадающие оценки.

Теорема 1. Для задачи DominatingSet достаточно n советских битов и необходимо n − 1 советских битов, чтобы быть оптимальным, для n ≥ 5.

Доказательство. Для верхней оценки алгоритм просто читает один советский бит на каждую раскрытую вершину и принимает её тогда и только тогда, когда бит равен 1.

Для нижней оценки противник раскрывает n − 1 изолированных вершин v1, ..., vn−1. После этого он раскрывает последнюю вершину vn, которая соединена с подмножеством V′ ⊆ {v1, v2, ..., vn−1} размера не менее 2. Это означает, что единственным оптимальным решением является V \ V′, потому что любое оптимальное решение должно содержать все изолированные вершины, то есть все вершины из {v1, ..., vn−1} \ V′, плюс по крайней мере одну вершину из компоненты C, индуцированной V′ ∪ {vn}. Поскольку |C| ≥ 3, единственной вершиной, которая доминирует над всеми вершинами в C, является vn.

Каждый выбор V′, то есть каждый возможный входной экземпляр, требует разного вывода алгоритма на первых n − 1 вершинах, и любые два экземпляра неразличимы до самого последнего раскрытия вершины. Существует 2n−1 − n возможных подмножеств V′, и мы имеем ⌈log(2n−1 − n)⌉ > ⌈log(2n−1 − 2n−2)⌉ = ⌈log(2n−2)⌉ = n − 2, где неравенство выполняется для всех n ≥ 5. Таким образом, необходимо по крайней мере n − 1 советских битов.

4. Рандомизация

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

В общем случае, когда допускаются экземпляры, содержащие изолированные вершины, легко видеть, что для рандомизированных алгоритмов нижняя оценка на конкурентное отношение из Теоремы 1 остаётся в силе. Действительно, на первых n − 1 запросах рандомизированный алгоритм R не может отличить два следующих экземпляра: I1, состоящий из n изолированных вершин, и I2, состоящий из звезды, в которой первые n − 1 вершин соединены с центральной вершиной, представленной на последнем запросе. Чтобы вычислить корректное решение для I1, алгоритм должен принимать каждую из первых n − 1 вершин с вероятностью 1, но тогда он достигает строгого конкурентного отношения n − 1 на I2.

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

Лемма 1 [Böckenhauer et al., 2011]. Рассмотрим онлайн-задачу минимизации U и пусть I(n) — количество всех возможных входов длины n. Далее, предположим, что существует рандомизированный онлайн-алгоритм для U с наихудшим ожидаемым конкурентным отношением не более E. Тогда для любого фиксированного ε > 0 можно построить детерминированный онлайн-алгоритм, использующий не более
log n + 2 log log n + log( log I(n) / log(1 + ε) ) + d
советских битов (для некоторой константы d) и достигающий конкурентного отношения (1 + ε)E.

Вместе с Теоремой 2 это даёт следующую нижнюю оценку.

Теорема 5. Любой рандомизированный онлайн-алгоритм для задачи DominatingSet на деревьях имеет наихудшее ожидаемое конкурентное отношение не менее (3/2) · (1 − δ) на достаточно больших экземплярах, для любого сколь угодно малого δ > 0.

5. Пути и циклы

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

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

В дальнейшем мы будем считать, что путь ориентирован, и его вершины занумерованы слева направо: v1, ..., vn.

Теорема 6. Никакой детерминированный онлайн-алгоритм для DominatingSet на путях не может быть лучше чем строго (1.5 − ε)-конкурентным, для произвольно малого ε > 0.

Теорема 7. На путях размера n жадный алгоритм для DominatingSet является:
• строго (1.5(1 + 1/n))-конкурентным, если n ≡ 3 (mod 6),
• строго 1.5-конкурентным в остальных случаях.

С одним советским битом мы можем построить алгоритм, который всегда является 1.5-конкурентным.

Теорема 8. Существует строго 1.5-конкурентный онлайн-алгоритм A для DominatingSet на путях, читающий один советский бит b.

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

Теорема 9. Для DominatingSet на путях достаточно (log 3)n/3 + O(log n) ≈ 0.5283n + O(log n) советских битов, чтобы быть оптимальным.

Интересно, что ту же технику можно использовать для установления совпадающей нижней оценки.

Теорема 10. Для DominatingSet на путях необходимо (log 3)n/3 − O(1) ≈ 0.5283n − O(1) советских битов, чтобы быть оптимальным.

Аналогичные методы можно использовать для получения следующих оценок для циклов. Опять же, мы обозначаем вершины как v1, ..., vn, а рёбра — как {vi, v(i mod n) + 1}, для 1 ≤ i ≤ n. Напомним, что G обозначает жадный алгоритм.

Теорема 11. Для DominatingSet на циклах G является строго 1.5-конкурентным.

Теорема 12. Для DominatingSet на циклах достаточно (log 3)n/3 + O(log n) ≈ 0.5283n + O(log n) и необходимо (log 3)n/3 − O(1) ≈ 0.5283n − O(1) советских битов, чтобы быть оптимальным.

6. Торы

В некотором смысле, пути — это «одномерный» класс графов. Расширив их до двух измерений путём взятия декартова произведения двух путей, мы получим класс решёток. Графы-решётки возникают в различных контекстах, например, в автоматизированном проектировании микросхем, как идеализированные модели уличных сетей городов или для моделирования задач редактирования строк.

Однако исследование доминирующих множеств на решётках трудоёмко и требует анализа по случаям, поскольку доминирующие множества часто распределены очень нерегулярно. Это происходит потому, что решётка имеет границы, и вершины в верхнем/левом углу не соединены напрямую с вершинами в нижнем/правом углу, иными словами, граф не является вершинно-симметричным. Этой проблемы можно избежать, просто убрав границы, или, точнее, соединив вершины на противоположных границах решётки; в результате получается тор.

Мы рассматриваем тор Tm,m размера m × m, для m ∈ ℕ+, то есть граф (V, E) с V = {vi,j | 1 ≤ i,j ≤ m} и E = { {vi,j, v}, {v, v} | 1 ≤ i,j ≤ m }.

Если m кратно 5, существует ровно десять оптимальных решений, которые все состоят из повторяющихся паттернов, показанных на Рисунке 6. То есть, в каждой строке и столбце каждая пятая вершина принадлежит оптимальному решению. Десять решений возникают из-за двух степеней свободы: во-первых, можно зеркально отразить паттерн, и, во-вторых, можно выбрать горизонтальное смещение относительно v1,1 (от 0 до 4). Эти решения оптимальны, потому что замкнутые окрестности вершин не пересекаются. Легко видеть, что других способов покрыть тор непересекающимися замкнутыми окрестностями единичных вершин не существует; таким образом, эти десять решений действительно являются единственными оптимальными.

7. Максимальные внешне-планарные графы

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

Определение 6. Граф G = (V, E) называется максимальным внешне-планарным, если существует планарное вложение G, при котором все вершины инцидентны внешней грани, и не существует такого планарного вложения для графа (V, E ∪ {e}) ни для какого ребра e ∉ E.

Мы приводим как верхнюю, так и нижнюю оценку сложности совета.

Теорема 15. Для задачи DominatingSet на максимальных внешне-планарных графах достаточно H(1/3)n + O(log n) ≈ 0.9183n + O(log n) советских битов для оптимальности.

Теорема 16. Для задачи DominatingSet на максимальных внешне-планарных графах необходимо 0.5n − O(1) советских битов для оптимальности.

8. Графы ограниченной степени

В этом последнем разделе мы рассматриваем графы, у которых максимальная степень вершин равна d.

Теорема 17. Для задачи DominatingSet на графах размера n с максимальной степенью d необходимо по крайней мере (d − 1)n/(d + 1) советских битов для оптимальности.

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

9. Заключение

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

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

Открытыми проблемами остаются сокращение разрыва между верхними и нижними оценками для торов и максимальных внешне-планарных графов, а также обобщение результатов на задачу вычисления почти оптимального решения (c-конкурентность).

Литература

  1. Alanko S. et al. Computing the domination number of grid graphs // Electron. J. Comb. – 2011.
  2. Barhum K. et al. On the power of advice and randomization for the disjoint path allocation problem // SOFSEM 2014. – LNCS 8327. – Springer, 2014. – P. 89–101.
  3. Böckenhauer H.-J., Benz N.C., Komm D. Call admission problems on trees with advice // IWOCA 2019. – LNCS 11638. – Springer, 2019. – P. 108–121.
  4. Bianchi M.P. et al. Online coloring of bipartite graphs with and without advice // COCOON 2012. – LNCS 7434. – Springer, 2012. – P. 519–530.
  5. Böckenhauer H.-J. et al. The string guessing problem as a method to prove lower bounds on the advice complexity // COCOON 2013. – LNCS 7936. – Springer, 2013. – P. 493–504.
  6. Böckenhauer H.-J. et al. The string guessing problem as a method to prove lower bounds on the advice complexity // Theor. Comput. Sci. – 2014. – Vol. 554. – P. 95–108.
  7. Böckenhauer H.-J. et al. On the advice complexity of the k-server problem // ICALP 2011. – LNCS 6755. – Springer, 2011. – P. 207–218.
  8. Böckenhauer H.-J. et al. On the advice complexity of online problems // ISAAC 2009. – LNCS 5878. – Springer, 2009. – P. 331–340.
  9. Böckenhauer H.-J. et al. Online algorithms with advice: the tape model // Inf. Comput. – 2017. – Vol. 254. – P. 59–83.
  10. Böckenhauer H.-J. et al. On the advice complexity of the knapsack problem // Theor. Comput. Sci. – 2014. – Vol. 527. – P. 61–72.
  11. Böckenhauer H.-J., Komm D., Wegner R. Call admission problems on grids with advice // WAOA 2018. – LNCS 11312. – Springer, 2018. – P. 118–133.
  12. Borodin A., El-Yaniv R. Online Computation and Competitive Analysis. – Cambridge University Press, 1998.
  13. Boyar J. et al. Online dominating set // Algorithmica. – 2019. – Vol. 81, No. 5. – P. 1938–1964.
  14. Boyar J. et al. Online algorithms with advice: a survey // ACM Comput. Surv. – 2017. – Vol. 50, No. 2. – P. 19.
  15. Boyar J. et al. The advice complexity of a class of hard online problems // Theory Comput. Syst. – 2017. – Vol. 61, No. 4. – P. 1128–1177.
  16. Boyar J. et al. Weighted online problems with advice // Theory Comput. Syst. – 2018. – Vol. 62, No. 6. – P. 1443–1469.
  17. Boyar J. et al. Online bin packing with advice // Algorithmica. – 2016. – Vol. 74, No. 1. – P. 507–527.
  18. Dobrev S., Královic̆ R., Pardubská D. How much information about the future is needed? // SOFSEM 2008. – LNCS 4910. – Springer, 2008. – P. 247–258.
  19. Dorrigiv R., He M., Zeh N. On the advice complexity of buffer management // ISAAC 2012. – LNCS 7676. – Springer, 2012. – P. 136–145.
  20. Eidenbenz S. Online dominating set and variations on restricted graph classes. – Technical Report 380, ETH Zürich, 2002.
  21. Elias P. Universal codeword sets and representations of the integers // IEEE Trans. Inf. Theory. – 1975. – Vol. 21, No. 2. – P. 194–203.
  22. Emek Y. et al. Online computation with advice // Theor. Comput. Sci. – 2011. – Vol. 412, No. 24. – P. 2642–2656.
  23. Gupta S., Kamali S., López-Ortiz A. On advice complexity of the k-server problem under sparse metrics // SIROCCO 2013. – LNCS 8179. – Springer, 2013. – P. 55–67.
  24. Haynes T.W., Hedetniemi S., Slater P. Fundamentals of Domination in Graphs. – Chapman & Hall/CRC, 1998.
  25. Hoffman F., Hadlock F.O. Block patterns and routing // Proc. of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing. – 1975.
  26. Hromkovic̆ J., Královic̆ R., Královic̆ R. Information complexity of online problems // MFCS 2010. – LNCS 6281. – Springer, 2010. – P. 24–36.
  27. King G.-H., Tzeng W.-G. On-line algorithms for the dominating set problem // Inf. Process. Lett. – 1997. – Vol. 61. – P. 11–14.
  28. Komm D. An Introduction to Online Computation. – Springer, 2016.
  29. Marshall C.W. Applied Graph Theory. – Wiley, 1971.
  30. Randomization can be as helpful as a glimpse of the future in online computation // ICALP 2016. – LIPIcs 55. – Schloss Dagstuhl, 2016. – P. 39.
  31. Renault M.P., Rosén A. On online algorithms with advice for the k-server problem // WAOA 2011. – LNCS 7164. – Springer, 2011. – P. 198–210.
  32. Schmidt J.P. All highest scoring paths in weighted grid graphs and their applications to finding all approximate repeats in strings // SIAM J. Comput. – 1998. – Vol. 27, No. 4. – P. 972–992.
  33. Seibert S., Sprock A., Unger W. Advice complexity of the online coloring problem // CIAC 2013. – LNCS 7878. – Springer, 2013. – P. 345–357.
  34. Steffen B. Advice Complexity of Online Graph Problems. – PhD thesis, ETH Zurich, 2014.