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

Элкин и Пелег [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> описывается соотношением Р(к, e) = KbglogK-loge.

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