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

Основной открытый вопрос заключается в том, возможно ли получить сходные результаты при <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].