https://ru.wikipedia.org/wiki/Алгоритм_Борувки
вот тут есть такая цитата
" Существует также рандомизированный алгоритм построения минимального остовного дерева, основанный на алгоритме Борувки, работающий в среднем за линейное время."
Но найти никакую информацию по этому алгоритму не могу.
Может кто в курсе что это такое?

на английской вики смотрел?

http://en.wikipedia.org/wiki/Bor?vka%27s_algorithm

boruvka's algorithm

(1)(2)(3)
Там вроде тоже только сама Борувка. А рандомизированной модификации нет.

Это не то?
Chazelle, Bernard (2000). "A minimum spanning tree algorithm with inverse-Ackermann type complexity". J. ACM 47 (6): 1028–1047. doi:10.1145/355541.355562.

или это
Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1 March 1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM 42 (2): 321–328. doi:10.1145/201019.201022

http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CBwQFjAA&url=http%3A%2F%2Fcs.brown.edu%2Fresearch%2Fpubs%2Fpdfs%2F1995%2FKarger-1995-RLT.pdf&ei=MRdrVOG1COXqyQOQ04K4BQ&usg=AFQjCNHo_uCMLINZ0sjd1DRtdKOkdaxl5Q&sig2=-KgctUobhB2XQRyL7Zc6PA&bvm=bv.79908130,d.bGQ

(7) О! Спасибо! Оно!

(6) загуглил строк (6)

(9) Странно что в русской вики не дали сноску.

(10) потому что на русском нет такой статьи. Да и вообще русская вики в 10 раз меньше английской

(10) Нету - так добавь )))

Теперь усложняем :)
Есть граф, есть фиксированный набор добавляемых вершин.
Какие есть хорошие алгоритмы нахождения приближений решения задачи Штейнера, лучших чем минимальный остов?

Мне в голову приходит только жадный алгоритм. Пока можем добавлять вершины которые дают результат лучший чем достигнутый, добавляем вершину дающую максимальный результат.
В качестве начального результата берем минимальный остов. Но жадный алгоритм слишком медленный. Надо быстрее.

(13) а веса новых рёбер чему равны?

(15) Заданы. Всякому равны. Это "скрытые" вершины графа, которые можно открывать. Веса всех ребер естественно положительны, граф не направленный

Я даже (14) в инете не видел, хотя это первое что приходит в голову. Пишут что задача NP-полная (для поиска точного решения), и что можно приблизительно получить результат посчитав минимальный остов. И всё.
Граф не планарный (полный).