4501
правка
Разреженные остовы графов: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 6: | Строка 6: | ||
== Основные результаты == | == Основные результаты == | ||
Элкин и Пелег [6] установили существование и возможность эффективного построения (1 + | Элкин и Пелег [6] установили существование и возможность эффективного построения <math>(1 + \epsilon, \; \beta)</math>-остовов размера <math>O(\beta \; n^{1 + 1/ \kappa }) \;</math> для любого n-вершинного графа G, где <math>\beta = \beta (\epsilon, \kappa) \;</math> константно, если <math>\kappa \;</math> и <math>\epsilon \;</math> также константны. Зависимость <math>\beta \;</math> от <math>\kappa \;</math> и <math>\epsilon \;</math> описывается соотношением <math>\beta (\kappa, \epsilon) = \kappa^{log \; log \; \kappa - log \; \epsilon}</math>. | ||
Важной составляющей построения остова в [6] является разбиение графа на области меньшего диаметра таким образом, чтобы суперграф, порожденный этими областями, был разреженным. Исследование таких разбиений было инициировано Авербухом [2], использовавшим их для синхронизации сетей. Пелег и Шеффер [ ] первыми | Важной составляющей построения остова в [6] является разбиение графа на области меньшего диаметра таким образом, чтобы [[суперграф]], порожденный этими областями, был разреженным. Исследование таких разбиений было инициировано Авербухом [2], использовавшим их для синхронизации сетей. Пелег и Шеффер [8] первыми применили подобные разбиения для построения остовов. В частности, они построили <math>(O(\kappa), \; 1)</math>-остовы с <math>O(n^{1 + 1/ \kappa }) \;</math> ребрами. Альтхофер и др. [1] предложили альтернативное доказательство результата Пелега и Шеффера, использующее элегантный «жадный» подход. При помощи этого подхода Альтхоферу и коллегам также удалось расширить свой результат на взвешенные графы, что позволило улучшить скрытую в O-нотации константу в алгоритме Пелега и Шеффера и получить сопутствующие результаты для планарных графов. | ||
== Применение == | == Применение == | ||
Эффективные алгоритмы вычисления разреженных (1 + | Эффективные алгоритмы вычисления разреженных <math>(1 + \epsilon, \; \beta)</math>-остовов были разработаны в [5] и [11]. Алгоритм из [5] использовался в работах [5, 7, 10] для вычисления приближенно кратчайших путей в централизованной, распределенной, потоковой и динамической централизованной моделях вычислений. Базовый подход, использовавшийся в этих работах, заключался в построении разреженного остова и последующем вычислении точных кратчайших путей в построенном остове. Разреженность последнего гарантирует, что вычисление кратчайших путей в остове будет намного эффективнее, чем в исходном графе. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Основной открытый вопрос заключается в том, возможно ли получить сходные результаты | Основной открытый вопрос заключается в том, возможно ли получить сходные результаты при <math>\epsilon = 0 \;</math>. Более формально, верно ли, что для любого <math>\kappa \ge 1 \;</math> и любого n-вершинного графа существует <math>(1, \; \beta (\kappa))</math>-остов G с <math>O(n^{1 + 1/ \kappa}) \;</math> ребрами? Для значений <math>\kappa \;</math>, равных 2 и 3, в работах [3, 4, 6] на этот вопрос был дан утвердительный ответ. Некоторые нижние границы недавно были доказаны Вудруффом [12]. | ||
Менее острая проблема заключается в улучшении соотношения зависимости | |||
Менее острая проблема заключается в улучшении соотношения зависимости <math>\beta \;</math> от <math>\epsilon \;</math> и <math>\kappa \;</math>. Некоторого прогресса в этом отношении достигли Торуп и Цвик [11], а также Петти [9]. | |||
== См. также == | == См. также == | ||
