Как найти минимальное остовное дерево в полном неориентированном графе?

Имеется полный неориентированный граф, в котором около 10000 вершин. Есть ли лучший способ найти минимальное остовное дерево, чем алгоритм Крускала, алгоритм Прима или Алгоритм Борувки?


graph algorithm minimum-spanning-tree
person Max    schedule 02.03.2015    source источник
comment
Prim с пользовательской очередью приоритетов, использующей плотность, имеет время O (n ^ 2), но каждый раз, когда я видел подобный вопрос в прошлом, это было так, что веса ребер являются евклидовыми расстояниями или что-то в этом роде. Это так и для вас?   -  person David Eisenstat    schedule 02.03.2015
comment
@DavidEisenstat, да, это тоже мой случай. Я использую евклидовы расстояния.   -  person Max    schedule 02.03.2015
comment
Сколько измерений?   -  person David Eisenstat    schedule 02.03.2015
comment
@DavidEisenstat, есть 2 измерения.   -  person Max    schedule 02.03.2015