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

В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера <math>O(n^{\frac{3}{2}})</math> и 3-остов размера O(n log n). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем исполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время <math>O(n log n + \frac{n}{εd})</math>. Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.