4501
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 14:30, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 27 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
Ключевые слова и синонимы: [[графовые алгоритмы]]; [[рандомизированные алгоритмы]]; [[кратчайший путь]]; [[остов]] | Ключевые слова и синонимы: [[графовые алгоритмы]]; [[рандомизированные алгоритмы]]; [[кратчайший путь]]; [[остов]] | ||
== Постановка задачи == | == Постановка задачи == | ||
[[Остов]] – это ''разреженный'' подграф данного неориентированного графа, сохраняющий приближенные расстояния между каждой парой вершин. Более точно, t-остов графа G = (V, E) представляет собой подграф (V, | [[Остов]] – это ''разреженный'' [[подграф]] данного [[неориентированный граф|неориентированного графа]], сохраняющий приближенные расстояния между каждой парой вершин. Более точно, t-остов графа <math>G = (V, E)\, </math> представляет собой подграф <math>(V, E_{s}), E_{s} \subseteq E \, </math>, такой, что для любой пары вершин расстояние между ними в подграфе не более чем в t раз больше расстояния между ними в исходном графе; при этом t называется [[коэффициент растяжения|коэффициентом растяжения]]. Формальное определение остовам дали Пелег и Шеффер [14], хотя связанные с ними понятия неявно использовал Авербух [3] в контексте сетевых синхронизаторов. | ||
Вычисление t-остова наименьшего размера для заданного графа представляет собой важную комбинаторную задачу с множеством вариантов применения. Однако вычисление t-остова наименьшего размера для графа является NP-полной задачей. Фактически (для значений t > 2) NP-полной [10] является даже задача аппроксимации минимального размера t-остова для графа с коэффициентом O(2<math>^{(1-\mu ) ln n)}</math>) | Вычисление t-остова наименьшего размера для заданного графа представляет собой важную комбинаторную задачу с множеством вариантов применения. Однако вычисление t-остова наименьшего размера для графа является NP-полной задачей. Фактически (для значений t > 2) NP-полной [10] является даже задача аппроксимации минимального размера t-остова для графа с коэффициентом O(2<math>^{(1-\mu ) ln \; n)}\, </math>) для любого <math>\mu</math> > 0. Осознав этот факт, исследователи предпочли двинуться в другом направлении, которое оказалось интересным и полезным. Пусть <math>S_{G}^{t}\, </math> – размер наиболее разреженного t-остова графа G, а <math>S_{n}^{t}\, </math> – максимальное значение <math>S_{G}^{t}\, </math> среди всех возможных графов с n вершинами. Существует ли алгоритм с полиномиальным временем выполнения, который для любого взвешенного графа и параметра t вычисляет его t-остов размера <math>O(S_{G}^{t})\, </math>? Такой алгоритм был бы лучшим из того, на что мы могли бы надеяться, учитывая сложность исходной задачи t-остова. Возникает естественный вопрос: насколько велико может быть значение <math>S_{G}^{t}\, </math>? Из высказанной Эрдосом [12] 43 года назад гипотезы о нижней границе обхвата следует, что существуют графы с n вершинами, для которых 2k-остов и (2k–1)-остов состоят из <math>\Omega (n^{1+\frac{1}{k}}) \, </math> ребер. Эта гипотеза была доказана для k = 1, 2, 3 и 5. Заметим, что (2k–1)-остов является также и 2k-остовом, а нижняя граница размера одинакова для 2k-остова и (2k–1)-остова. Таким образом, задача заключается в разработке алгоритма, который для любого взвешенного графа с n вершинами вычисляет (2k–1)-остов размера <math>O(n^{1+\frac{1}{k}}) \, </math>. Разумеется, хотелось бы найти самый быстрый алгоритм решения этой задачи, а наиболее амбициозная цель заключается в нахождении алгоритма линейной сложности. | ||
для любого <math>\mu</math> > 0. Осознав этот факт, исследователи предпочли двинуться в другом направлении, которое оказалось интересным и полезным. Пусть <math>S_{G}^{t}</math> – | |||
размер наиболее разреженного t-остова графа G, а <math>S_{n}^{t}</math> – максимальное значение <math>S_{G}^{t}</math> среди всех возможных графов с n вершинами. Существует ли алгоритм с полиномиальным временем | |||
== Основные результаты == | == Основные результаты == | ||
В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и | В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и ребер графа G, соответственно. Первый алгоритм, разработанный Альтхофером и коллегами [2], основан на [[жадный алгоритм|жадной стратегии]] и выполняется за время <math>O(mn^{1+\frac{1}{k}})</math>. Второй алгоритм [6] основан на сверхлокальном подходе, он выполняется за время O(km). Для начала рассмотрим следующее простое наблюдение. Предположим, что имеется подмножество <math>E_{s} \in E</math>, такое, что для каждого ребра <math>(x, y) \in E \setminus E_{s}</math> выполняется следующее утверждение. | ||
P<math>_{t}</math>(x, y): вершины x и y связаны в подграфе (V, E<math>_{S}</math>) путем, состоящим из не более чем t | P<math>_{t}</math>(x, y): вершины x и y связаны в подграфе (V, E<math>_{S}</math>) путем, состоящим из не более чем t ребер, причем вес каждого ребра на этом пути не превышает вес ребра (x, y). | ||
Из этого напрямую следует, что подграф (V, E<math>_{S}</math>) будет t-остовом для G. Два алгоритма вычисления (2k–1)-остова способны вычислить множество E<math>_{S}</math> при помощи двух совершенно разных подходов. | Из этого напрямую следует, что подграф (V, E<math>_{S}</math>) будет t-остовом для G. Два алгоритма вычисления (2k–1)-остова способны вычислить множество E<math>_{S}</math> при помощи двух совершенно разных подходов. | ||
== Алгоритм I == | == Алгоритм I == | ||
Этот алгоритм выбирает | Этот алгоритм выбирает ребра для остова по принципу жадности; он напоминает алгоритм Крускала для вычисления минимального остовного дерева. Ребра графа обрабатываются в порядке возрастания их весов. Начиная с остова <math>E_{S} = \varnothing</math>, алгоритм последовательно добавляет ребра. Решение о том, добавлять ли некоторое ребро (скажем, <math>(u, v) \, </math>) к <math>E_{S} \, </math> или нет, принимается на основе следующего соображения: | ||
''Если расстояние между u и v в подграфе, индуцированном текущими ребрами остова <math>E_{S} \, </math>, больше, чем t-weight(M, v), то ребро (u, v) следует добавить к to <math>E_{S} \, </math>, в противном случае отбросить.'' | |||
Из этого следует, что <math>P_{t}(x, y) \, </math> будет выполняться для каждого ребра E, не входящего в <math>E_{S} \, </math>, так что в конце концов подграф <math>(v, E_{S}) \, </math> будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем <math>n^{1+\frac{1}{k}}</math> ребрами должен содержать цикл длиной не более 2k. Из приведенного выше алгоритма следует, что длина любого цикла в подграфе <math>(V, E_{S}) \, </math> должна составлять не менее t + 1. Следовательно, для t = 2k – 1 количество ребер в подграфе <math>(V, E_{S}) \, </math> будет менее <math>n^{1+\frac{1}{k}}</math>. Таким образом, Алгоритм I вычисляет (2k–1)-остов размера <math>O(n^{1+\frac{1}{k}})</math>, что является оптимальным, с учетом вышеупомянутой нижней границы. | |||
Простая реализация Алгоритма I размера | Простая реализация Алгоритма I размера <math>O(mn^{1+\frac{1}{k}})</math> разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем выполнения – <math>O(kmn^{\frac{1}{k}})</math>. Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени выполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени выполнения. | ||
== Алгоритм II == | == Алгоритм II == | ||
Алгоритм выполняет оригинальную кластеризацию на основе сверхлокального подхода и устанавливает следующий результат для задачи нахождения остова. | Алгоритм выполняет оригинальную кластеризацию на основе сверхлокального подхода и устанавливает следующий результат для задачи нахождения остова. | ||
Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером | Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером <math>O(kn^{1+\frac{1}{k}})</math> может быть вычислен за время O(km). | ||
Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных | Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных ребер. Для доказательства простоты алгоритма далее приводятся его полная версия для нахождения 3-остова и анализ алгоритма. Алгоритм может быть легко адаптирован к другим вычислительным моделям (с параллельной, внешней или распределенной памятью) с сохранением почти оптимальной производительности (подробнее см. в [6]). | ||
== Вычисление 3-остова за линейное время == | == Вычисление 3-остова за линейное время == | ||
Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> | Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> ребер. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их ребра могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на [[доминирующее множество|доминирующих множествах]]. | ||
Вначале имеется множество | |||
Вначале имеется множество ребер E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает ребра E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа. | |||
1. Формирование кластеров: | '''1. Формирование кластеров:''' | ||
Выборка R | |||
(a) | Выборка <math>R \subset V</math> выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u}<math>\mid</math>u <math>\in </math>R}. Каждая вершина <math>u \in R</math> называется центром своего кластера. Каждая невыбранная вершина <math>v \in V - R</math> обрабатывается следующим образом: | ||
(b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего | (a) Если v не является смежной с какой-либо выбранной вершиной, то каждое ребро, инцидентное v, перемещается в E<math>_{S}</math>. | ||
На последнем шагу первого этапа все | (b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего к v соседа из числа выбранных вершин (связи можно разрывать произвольным образом; однако ради удобства можно считать, что все веса различны.). Ребро (v , N(v, R)) и каждое инцидентное v ребро с весом, меньшим, чем у этого ребра, перемещаются в E<math>_{S}</math>. Затем вершина v добавляется в кластер с центром в N(v, R). | ||
На последнем шагу первого этапа все ребра (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются. | |||
Пусть V’ – множество вершин, соответствующих конечным точкам ребер E’, оставшимся после завершения первого этапа. Из этого следует, что каждая вершина из V’ является либо вершиной из выборки, либо смежной с одной из таких вершин, и этап 1(b) разбивает V' на непересекающиеся кластеры, в центре каждого из которых находится некоторая вершина из выборки. Заметим, что вследствие последнего этапа каждое ребро в множестве E’ является внутрикластерным ребром. Граф (V’, E’) т соответствующее разбиение V’ на кластеры передается на вход следующего (второго) этапа. | |||
'''2. Соединение вершин с соседними кластерами:''' | |||
Каждая вершина v графа (V’, E’) обрабатывается следующим образом. | Каждая вершина v графа (V’, E’) обрабатывается следующим образом. | ||
Пусть E’(v, c) – | Пусть E’(v, c) – ребра из множества E’, инцидентные v, из кластера c. Для каждого кластера c, являющегося соседом v, ребро из E’(v, c) с наименьшим весом перемещается в E<math>_{S}</math>; остальные ребра отбрасываются. | ||
Количество | Количество ребер, добавленных к остову E<math>_{S}</math> за время выполнения описанных этапов алгоритма, можно ограничить следующим образом. Заметим, что множество выборки R формируется путем случайного и независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Из элементарной вероятности следует, что для каждой вершины <math>v \in V</math> ожидаемое количество инцидентных ей ребер с весами меньше, чем у (v, N (v, R)), не превосходит <math>\sqrt{n}</math>. Таким образом, ожидаемое количество ребер, вносимых в остов каждой вершиной на первом этапе алгоритма, не превосходит <math>\sqrt{n}</math>. Количество ребер, добавленных к остову на второй фазе, составляет O(n<math>\mid</math>R<math>\mid</math>). Поскольку ожидаемый размер выборки R равен <math>\sqrt{n}</math>, следовательно, ожидаемое количество ребер, добавленных к остову на второй фазе, составляет не более n<math>^{3/2}</math>. Следовательно, ожидаемый размер остова E<math>_{S}</math> по окончании работы Алгоритма II в вышеописанном виде не превосходит 2n<math>^{3/2}</math>. Алгоритм выполняется повторно, если размер остова превосходит 3n<math>^{3/2}</math>. Из неравенства Маркова следует, что ожидаемое количество таких повторений будет составлять O(1). | ||
Установим теперь, что E<math>_{S}</math> является 3-остовом. Заметим, что для каждого ребра edge (u, v) <math>\notin</math> E<math>_{S}</math>, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев. | |||
Случай | ''Случай 1: (u и v принадлежат к одному кластеру)'' | ||
Пусть в начале второго этапа (u, v’) | Пусть u и v принадлежат к одному кластеру с центром x <math>\in</math> R. Из первой фазы алгоритма следует, что существует путь из двух ребер u – x – v в остове, причем каждое из этих ребер не тяжелее ребра (u, v). (Этот факт дает обоснование для отбрасывания всех внутрикластерных ребер в конце первого этапа). | ||
Алгоритм вычисления (2k–1)-остова | |||
''Случай 2: (u и v принадлежат к разным кластерам)'' | |||
Очевидно, что ребро (u, v) была удалена из E’ на этапе 2; предположим, что она была удалена при обработке вершины u. Пусть вершина v входит в кластер с центром x <math>\in</math> R. | |||
Пусть в начале второго этапа (u, v’) <math>\in</math> E’ будет ребром с наименьшим весом среди всех ребер, инцидентных u, от вершин кластера с центром в x. Таким образом, должно выполняться weight(u, v’) ≤ weight(u, v). Обработка вершины u на втором этапе алгоритма гарантирует, что ребро (u, v’) добавляется в E<math>_{S}</math>. Следовательно, существует путь Π<math>_{uv}</math> = u – v’ – x – v между u и v в остове E<math>_{S}</math>, и его вес ограничен weight(Π<math>_{uv}</math>) = weight(u, v’) + weight(v’, x) + weight(x, v). Поскольку (v’, x) и (v, x) были выбраны на первом этапе, должно выполняться weight(v’, x) ≤ weight(u, v’) и weight(x, v) ≤ weight(u, v). Отсюда следует, что остов (v, E<math>_{S}</math>) имеет коэффициент растяжения 3. Кроме того, обе фазы алгоритма могут быть выполнены за время O(m) с использованием элементарных структур данных и блочной сортировки. | |||
Алгоритм вычисления (2k–1)-остова выполняет k итераций, причем каждая итерация напоминает первый этап алгоритма нахождения 3-остова. Детали и формальное доказательство можно найти в [6]. | |||
== Родственные работы == | |||
Понятие остова в обобщенном виде исследовалось во многих работах. | Понятие остова в обобщенном виде исследовалось во многих работах. | ||
Применение | ''Аддитивные остовы'': описанный выше t-остов аппроксимирует попарные расстояния с мультипликативной ошибкой; его мы будем называть ''мультипликативным остовом''. Аналогичным образом можно определить остов, аппроксимирующий попарные расстояния с аддитивной ошибкой. Такой остов называется аддитивным остовом, а соответствующая ошибка носит название ''избытка''. Эйнгворт и коллеги [1] представили первый аддитивный остов размера O(n<math>^{3/2 log n}</math>) с избытком 2. Босуана и коллеги [7] представили алгоритм построения аддитивного остова размера O(n<math>^{4/3}</math>) с избытком 6. До сих пор остается открытым вопрос, существуют ли более разреженные аддитивные остовы. | ||
Остовы исключительно полезны для многих приложений в таких областях, как распределенные системы и коммуникационные сети. В этих приложениях остовы являются основной графовой структурой. Для построения компактных таблиц маршрутизации [16] многие существующие алгоритмы маршрутизации используют | |||
''(α,β)-остов'': Элкин и Пелег [11] ввели понятие ''(α,β)-остова'' для невзвешенных графов, который можно рассматривать как гибрид мультипликативного и аддитивного остовов. (α,β)-остов представляет собой подграф, такой, что расстояние между любыми двумя вершинами u, v <math>\in</math> V в этом подграфе ограничено αδ(u, v) + β, где δ(u, v) – расстояние между вершинами u и v в исходном графе. Элкин и Пелег показали, что (1+ε, β)-остов размера O(βn<math>^{1+ \delta}</math>) для произвольно малых ε, δ > 0 может быть вычислен за счет достаточно большого значения избытка β. Недавно Торуп и Цвик [19] разработали остов с аддитивной ошибкой, сублинейной относительно аппроксимируемого расстояния. | |||
Среди других интересных вариантов остовов – ''остов с сохранением расстояния'', предложенный Боллобасом и коллегами [8], и ''легковесный остов'', предложенный Авербухом и коллегами [4]. Подграф называется d-хранителем, если он сохраняет точные расстояния между каждой парой вершин, разделенных расстоянием не менее d. Легковесный остов стремится минимизировать количество ребер и полный вес ребер. Параметр «''легкость''» определяется для подграфа как отношение полного веса всех его ребер к весу минимального остовного дерева графа. Авербух и коллеги [4] показали, что для любого взвешенного графа и целого числа k > 1 существует O(k)-остов с <math>O(k \rho n^{l+\frac{1}{k}})</math> ребрами и легкостью <math>O(k \rho n^{\frac{1}{k}})</math>, где <math>\rho\ </math> = log(Diameter), который можно построить за полиномиальное время. | |||
В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера <math>O(n^{\frac{3}{2}})</math> и 3-остов размера O(n log n). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем выполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время <math>O(n log n + \frac{n}{\epsilon^{d}})</math>. Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида. | |||
== Применение == | |||
Остовы исключительно полезны для многих приложений в таких областях, как распределенные системы и коммуникационные сети. В этих приложениях остовы являются основной графовой структурой. Для построения компактных таблиц маршрутизации [16] многие существующие алгоритмы маршрутизации используют ребра разреженного остова для маршрутизации сообщений. В распределенных системах остовы играют важную роль при разработке ''синхронизаторов''. Авербух [3] и Пелег и Ульман [15] показали, что качество остова (выражаемое в терминах коэффициента растяжения и количества ребер остова) тесно связано с временем и коммуникационной сложностью любого синхронизатора сети. Остовы также могут неявно использоваться во множестве алгоритмов для вычисления всех пар аппроксимированных кратчайших путей [5, 9, 18]. Примеры других приложений можно найти в работах [2, 3, 14, 16]. | |||
== Открытые проблемы == | |||
Время выполнения и размер (2k–1)-остова, вычисляемого Алгоритмом II, отличаются в k раз от соответствующих нижних границ для худшего случая. Для любого константного значения k оба эти параметра являются оптимальными. Однако для экстремального значения k, а именно – для k = log n, имеется отклонение с коэффициентом log n. Возможно ли избавиться от этого мультипликативного множителя k ко времени выполнения алгоритма и/или размеру вычисляемого (2k–1)-остова? Представляется, что для решения этой задачи могут быть полезны более тщательный анализ и передовые теоретико-вероятностные инструменты. | |||
== Литература == | |||
1. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28,1167-1181 (1999) | |||
2. Althofer, I., Das, G., Dobkin, D.P.,Joseph, D., Soares J.:On sparse spanners of weighted graphs. Discret. Comput. Geom. 9, 81-100(1993) | |||
2. Althofer, I., Das, G., Dobkin, D.P.,Joseph, D., Soares J.:On sparse spanners of weighted graphs. Discret. Comput. Geom. 9, 81-100(1993) | 3. Awerbuch, B.: Complexity of network synchronization. J. Assoc. | ||
3. Awerbuch, B.: Complexity of network synchronization. J. Assoc. | |||
Comput. Mach. 32(4), 804-823 (1985) | Comput. Mach. 32(4), 804-823 (1985) | ||
4. Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and lightweight spanners. Tech. Report CS92-22, Weizmann Institute of Science (1992) | |||
5. Awerbuch, B., Berger, B., Cowen, L., Peleg D.: Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28,263-277(1998) | 4. Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and lightweight spanners. Tech. Report CS92-22, Weizmann Institute of Science (1992) | ||
6. Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30, 532-563 (2007) | |||
7. Baswana, S., Telikepalli, K., Mehlhorn, K., Pettie, S.: New construction of (a, /J)-spanners and purely additive spanners. In: Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 672-681 | 5. Awerbuch, B., Berger, B., Cowen, L., Peleg D.: Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28,263-277(1998) | ||
8. Bollobas, B., Coppersmith, D., Elkin M.: Sparse distance preserves and additive spanners. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 414-423 | |||
9. Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. 28,210-236 (1998) | 6. Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30, 532-563 (2007) | ||
10. Elkin, M., Peleg, D.: Strong inapproximability of the basic k-spanner problem. In: Proc. of 27th International Colloquim on Automata, Languages and Programming, 2000, pp. 636-648 | |||
11. Elkin, M., Peleg, D.: (1 + e,/J)-spanner construction for general graphs. SIAM J. Comput. 33,608-631 (2004) | 7. Baswana, S., Telikepalli, K., Mehlhorn, K., Pettie, S.: New construction of (a, /J)-spanners and purely additive spanners. In: Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 672-681 | ||
12. Erdos, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pp. 29-36. Publ. House Czechoslovak Acad. Sci., Prague (1964) | |||
13. Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript (1996) | 8. Bollobas, B., Coppersmith, D., Elkin M.: Sparse distance preserves and additive spanners. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 414-423 | ||
14. Peleg, D., Schaffer, A.A.: Graph spanners. J. Graph Theory 13, 99-116(1989) | |||
15. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740-747 (1989) | 9. Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. 28,210-236 (1998) | ||
16. Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. Assoc. Comput Mach. 36(3), 510-530 (1989) | |||
17. Salowe, J.D.: Construction of multidimensional spanner graphs, with application to minimum spanning trees. In: ACM Symposium on Computational Geometry, 1991, pp. 256-261 | 10. Elkin, M., Peleg, D.: Strong inapproximability of the basic k-spanner problem. In: Proc. of 27th International Colloquim on Automata, Languages and Programming, 2000, pp. 636-648 | ||
18. Thorup, M., Zwick, U.: Approximate distance oracles. J. Assoc. Comput. Mach. 52,1-24 (2005) | |||
19. Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 802-809 | 11. Elkin, M., Peleg, D.: (1 + e,/J)-spanner construction for general graphs. SIAM J. Comput. 33,608-631 (2004) | ||
12. Erdos, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pp. 29-36. Publ. House Czechoslovak Acad. Sci., Prague (1964) | |||
13. Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript (1996) | |||
14. Peleg, D., Schaffer, A.A.: Graph spanners. J. Graph Theory 13, 99-116(1989) | |||
15. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740-747 (1989) | |||
16. Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. Assoc. Comput Mach. 36(3), 510-530 (1989) | |||
17. Salowe, J.D.: Construction of multidimensional spanner graphs, with application to minimum spanning trees. In: ACM Symposium on Computational Geometry, 1991, pp. 256-261 | |||
18. Thorup, M., Zwick, U.: Approximate distance oracles. J. Assoc. Comput. Mach. 52,1-24 (2005) | |||
19. Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 802-809 | |||