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

Элкин и Пелег [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-нотации константу в алгоритме Пелега и Шеффера и получить сопутствующие результаты для планарных графов.

 

Основной открытый вопрос заключается в том, возможно ли получить сходные результаты с 6 = 0. Более формально, верно ли, что для любого k > 1 и любого n-вершинного графа существует (1 fi(к))-остов G с O(n1+1/lc) ребрами? Для значений к, равных 2 и 3, в работах [3, 4, 6] на этот вопрос был дан утвердительный ответ. Некоторые нижние границы недавно были доказаны Вудруффом [12].

Менее острая проблема заключается в улучшении соотношения зависимости f$ от e и к. Некоторого прогресса в этом отношении достигли Торуп и Цвик [ ], а также Петти [9].