Разреженные остовы графов

Ключевые слова и синонимы

(1 + e, /S)-остовы; почти аддитивные остовы

Постановка задачи

Для пары чисел a, f$, a > 1, f$ > 0, подграф G0 = (V, H) невзвешенного неориентированного графа G = (V, E), H С E, является (a, /S)-остовом G, если для каждой пары вершин u, w 2 V distG0 (u, w) < a-disto(u, w)+P, где distG (u, w) обозначает расстояние между u и w в G. Мы хотим показать, что для каждого n-вершинного графа существует разреженный (a, /3)-остов с настолько малыми значениями a и f$, насколько это возможно. Задача заключается в нахождении асимптотического компромисса между a и f$, с одной стороны, и разреженностью остова – с другой.

Основные результаты

Элкин и Пелег [6] установили существование и возможность эффективного построения (1 + e, /3)-остовов размера O{f$nl+llK) для каждого n-вершинного графа G, где f$ = ;в(е, к) константно независимо от значений к и e. Зависимость £ от к и e описывается соотношением Р(к, e) = KbglogK-loge.

Важной составляющей построения остова в [6] является разбиение графа на области меньшего диаметра таким образом, чтобы суперграф, порожденный этими областями, был разреженным. Исследование таких разбиений было инициировано Авербухом [2], использовавшим их для синхронизации сетей. Пелег и Шеффер [ ] первыми использовали подобные разбиения для построения остовов. В частности, они построили (О(к), 1)-остовы с O(n1+1/lc) ребрами. Альтхофер и др. [ ] предложили альтернативное доказательство результата Пелега и Шеффера, использующее элегантный «жадный» аргумент. При помощи этого аргумента Альтхоферу и коллегам также удалось расширить свой результат на взвешенные графы, что позволило улучшить скрытую в O-нотации константу в алгоритме Пелега и Шеффера и получить сопутствующие результаты для планарных графов.

Применение

Эффективные алгоритмы вычисления разреженных (1 + e,jS)-остовов были разработаны в [5] и [11]. Алгоритм из [5] использовался в работах [5, 7, 10] для вычисления приближенно кратчайших путей в централизованной, распределенной, потоковой и динамической централизованной моделях вычислений. Базовый подход, использовавшийся в этих работах, заключался в построении разреженного остова и последующем вычислении точных кратчайших путей в построенном остове. Разреженность последнего гарантирует, что вычисление кратчайших путей в остове будет намного эффективнее, чем в исходном графе.

Открытые вопросы

Основной открытый вопрос заключается в том, возможно ли получить сходные результаты с 6 = 0. Более формально, верно ли, что для любого k > 1 и любого n-вершинного графа существует (1 fi(к))-остов G с O(n1+1/lc) ребрами? Для значений к, равных 2 и 3, в работах [3, 4, 6] на этот вопрос был дан утвердительный ответ. Некоторые нижние границы недавно были доказаны Вудруффом [12]. Менее острая проблема заключается в улучшении соотношения зависимости f$ от e и к. Некоторого прогресса в этом отношении достигли Торуп и Цвик [ ], а также Петти [9].

См. также

• Синхронизаторы, остовы

Литература

1. 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. Awerbuch, B.: Complexity of network synchronization. J. ACM 4,804-823(1985)

3. Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New Constructions of (alpha, beta)-spanners and purely additive spanners. In: Proc. of Symp. on Discrete Algorithms, Vancouver, Jan 2005, pp.672-681

4. Dor, D., Halperin, S., Zwick, U.: All Pairs Almost Shortest Paths. SIAM J. Comput. 29,1740-1759 (2000)

5. Elkin, M.: Computing Almost Shortest Paths. Trans. Algorithms 1(2),283-323(2005)

6. Elkin, M., Peleg, D.: (1 + e, /J)-Spanner Constructions for General Graphs. SIAM J. Comput. 33(3), 608-631 (2004)

7. Elkin, M., Zhang, J.: Efficient Algorithms for Constructing (1 + e, /J)-spanners in the Distributed and Streaming Models. Distrib. Comput. 18(5), 375-385 (2006)

8. Peleg, D., Schaffer, A.: Graph spanners. J. Graph Theory 13, 99-116(1989)

9. Pettie, S.: Low-Distortion Spanners. In: 34th International Colloquium on Automata Languages and Programm, Wroclaw, July 2007, pp. 78-89

10. Roditty, L., Zwick, U.: Dynamic approximate all-pairs shortest paths in undirected graphs. In: Proc. of Symp. on Foundations of Computer Science, Rome, Oct. 2004, pp. 499-508

11. Thorup, M., Zwick, U.: Spanners and Emulators with sublinear distance errors. In: Proc. of Symp. on Discrete Algorithms, Miami, Jan. 2006, pp. 802-809

12. Woodruff, D.: Lower Bounds for Additive Spanners, Emulators, and More. In: Proc. of Symp. on Foundations of Computer Science, Berckeley, Oct. 2006, pp. 389-398