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

Важной составляющей построения остова в [6] является разбиение графа на области меньшего диаметра таким образом, чтобы суперграф, порожденный этими областями, был разреженным. Исследование таких разбиений было инициировано Авербухом [2], использовавшим их для синхронизации сетей. Пелег и Шеффер [8] первыми использовали подобные разбиения для построения остовов. В частности, они построили <math>(O(\kappa), \; 1)</math>-остовы с <math>O(n^{1 + 1/ \kappa }) \;</math> ребрами. Альтхофер и др. [1] предложили альтернативное доказательство результата Пелега и Шеффера, использующее элегантный «жадный» аргумент. При помощи этого аргумента Альтхоферу и коллегам также удалось расширить свой результат на взвешенные графы, что позволило улучшить скрытую в O-нотации константу в алгоритме Пелега и Шеффера и получить сопутствующие результаты для планарных графов.