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

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