4446
правок
Разреженные остовы графов: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == (1 + e, /S)-остовы; почти аддитивные остовы == Постановка задач…») |
Irina (обсуждение | вклад) |
||
| (не показано 12 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
(1 + | <math>(1 + \epsilon, \; \beta)</math>-остовы; почти аддитивные остовы | ||
== Постановка задачи == | == Постановка задачи == | ||
Для пары чисел | Для пары чисел <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>, где <math>dist_G (u, w) \;</math> обозначает расстояние между u и w в G. Мы хотим показать, что для каждого n-вершинного графа существует разреженный <math>(\alpha, \; \beta)</math>-остов с настолько малыми значениями <math>\alpha \;</math> и <math>\beta \;</math>, насколько это возможно. Задача заключается в нахождении асимптотического компромисса между <math>\alpha \;</math> и <math>\beta \;</math>, с одной стороны, и разреженностью остова – с другой. | ||
== Основные результаты == | == Основные результаты == | ||
Элкин и Пелег [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]. | |||
== См. также == | == См. также == | ||
