Остовные деревья с низким растяжением: различия между версиями

Наиболее очевидный из открытых вопросов касается ликвидации разрыва между верхней границей O(log2 n log log n) и нижней границей Q(log n) значения avestr(n). Еще одна интересная тема – изучение остовных деревьев с низким растяжением для различных ограниченных семейств графов. В этом направлении недавно достигли заметного прогресса Эмек и Пелег [ ], построившие остовные деревья с низким растяжением со средним значением растяжения O(log n) для невзвешенных серийно-параллельных графов. Также обширным полем для исследований является нахождение других способов применения остовных деревьев с низким растяжением.

Наконец, имеется довольно близкое ослабленное понятие деревьев Штейнера или Бартала с низким растяжением. В отличие от остовных деревьев, дерево Штейнера не обязано быть подграфом исходного графа; оно может содержать ребра и вершины, не входящие в состав исходного графа. Однако при этом требуется, чтобы расстояния в дереве Штейнера были не меньше расстояний в исходном графе. Деревья Штейнера с низким растяжением широко исследовались [3, 4, 12]. Факхаренфол и коллеги [ ] разработали алгоритм построения деревьев Штейнера с низким растяжением со средним значением растяжения O(log n). В настоящее время неизвестно, будет ли техника, используемая при изучении деревьев Штейнера с низким растяжением, полезна при улучшении границ остовных деревьев с низким растяжением.