4501
правка
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
Строка 6: | Строка 6: | ||
== Основные результаты == | == Основные результаты == | ||
Элкин и Пелег [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> описывается соотношением | Элкин и Пелег [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-нотации константу в алгоритме Пелега и Шеффера и получить сопутствующие результаты для планарных графов. | ||
== Применение == | == Применение == |
правка