Разреженные остовы графов: различия между версиями

Для пары чисел <math>\alpha, \beta: \alpha \ge 1, \beta \ge 0 \;</math>, подграф <math>G' = (V, H) \;</math> невзвешенного неориентированного графа <math>G = (V, E), H \subseteq E \;</math>, является <math>(\alpha, \; \beta)</math>-остовом G, если для каждой пары вершин <math>u, w \in V \;</math> выполняется соотношение <math>dist_{G'} (u, w) \le \alpha \cdot dist_G (u, w) + \beta \;</math>, где distG (u, w) обозначает расстояние между u и w в G. Мы хотим показать, что для каждого n-вершинного графа существует разреженный <math>(\alpha, \; \beta)</math>-остов с настолько малыми значениями <math>\alpha \;a</math> и <math>\beta \;</math>, насколько это возможно. Задача заключается в нахождении асимптотического компромисса между <math>\alpha \;a</math> и <math>\beta \;</math>, с одной стороны, и разреженностью остова – с другой.

Элкин и Пелег [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].