最小費用全域木の計算

一般のグラフではChazelle (1997) のO(mα(m,n))時間アルゴリズムが知られてる中で最速．
乱数使用を許すとO(m)時間アルゴリズムがある．これはKarger-Klein-Tarjan (1995) の結果だけど，その中では与えられた全域木が最小費用全域木かどうかを判定する線形時間アルゴリズム (Dixon-Rauch-Tarjan, King) を用いている．