この記事は アドベントカレンダー2023 2 日目の記事です。

きのう :

アドベントカレンダー2023始まります

この記事はアドベントカレンダー2023 1日目の記事です。 アドベントカレンダー始まります 本日(2023/12/01)からtraPのアドベントカレンダー2023です。 traP部員が日常生活、大学の講義、ハマっている趣味などを書きます。 期間は2023/12/25までです。お楽しみに! 予定カレンダーの写真 (11/29時点) 上の表はあくまで予定であり、後で変更される可能性があります ブログが投稿されるたびにTwitterにお知らせツイートが流れるので是非フォローしてください！ https://twitter.com/traPtitech いかが…

東京工業大学デジタル創作同好会traPH1rono_K

アドベントカレンダー初日なのでクリスマスをネガキャンしよう！

この記事は、アドベントカレンダー2023 1日目の記事です。 はじめに こんにちは、聖夜の破壊者(クリスマス=デストロイヤー)です。ごめんなさい、YHz / イキリ虻です。 皆様はアドベントカレンダーの由来をご存じでしょうか？ もとは海外の風習で、12/1からクリスマスまでの25日の間、カレンダー状になった引き出しや箱を開封していき、クリスマスまでの間1日1つ中に入ったプレゼントを受け取っていく風習です。 これにちなんで、クリスマスまでの25日の間、みんなでブログを書こう！というのがインターネットの主要プラットフォームでのアドベントカレンダーブログリレーの始まりで、traPでも…

東京工業大学デジタル創作同好会traPYHz_ikiri

みなさん, 論文読んでますか？
論文読んでまとめて入門記事を作って、競プロに新しい風を吹かせて欲しいんですが…

FPS や Monge のようにマトロイドやその他色々な分野についてすべてをまとめてブログにしてくれる人が必要という話になった

— tatyam (@tatyam_prime) November 26, 2023

今日は研究をしていたらおもしろいのを見つけて, しかも短いのでここにまとめておきます.

A. C. Yao, An $O(|E|\log \log |V|)$ algorithm for finding minimum spanning trees, Inform. Process. Lett., 4 (1975); pp. 21--23.

論文の本質が 1 ページくらいしかなく, とても短い！
みなさんも読んでみてはいかがでしょうか？

問題 : 最小全域木問題

連結無向グラフ $G=(V,E)$ と辺重み $c:E\to \mathbb{R}$ が与えられる.
辺集合の部分集合 $E^{\prime }\subset E$ であって $(V,E^{\prime })$ が木になるもののうち, 辺重みの和 ${\sum }_{e\in E^{\prime }}c(e)$ が最小のものを求めよ.

アルゴリズム

より実用的・単純になるように整理したものがこちらになります.

パラメータ $k\in \mathbb{N}$ を取る. (後で適当な大きさに決定する.)

前処理

頂点 $v$ に隣接する辺の集合を $E_v$ とする. $E_v$ を辺重み $c(\cdot )$ で ざっくりソート する.
ざっくりソート とは, $E_v$ を要素数 $|E_v|/k$ 以下のいくつかのグループに分け, グループ内はソートされていなくても良いが, グループの間ではソートされているようにすること.
分けたグループを ${E_v}^{(1)},{E_v}^{(2)},\dots$ とすると, $\forall i<j,x\in {E_v}^{(i)},y\in {E_v}^{(j)}⟹c(x)\le c(y)$

クイックソートを途中でやめるとできる. $O(|E_v|\log k)$ 時間, 全体で $O(|E|\log k)$ 時間.

ブルーフカ法

ブルーフカ法をやる. 以下を全頂点が連結になるまで (最大 ${\log }_2|V|$ 回) 行う.

• $E_v\ne \varnothing$ であるような各頂点 $v\in V$ について, $E_v$ のうち辺の両端の頂点がまだ連結でない辺のうち, 重みが最小のものを見つける.
  • これは償却 $O(|E_v|/k\cdot \alpha (|V|))$ 時間でできる. 最も辺重みが小さいグループについて, すでに両端が連結であるような辺を Union-Find で判定して取り除いたあと, 重みが最小の辺を線形探索する. すべての辺が削除されてしまった場合は, 次に辺重みが小さいグループを取り出し, これを繰り返す.
• この情報を集約し, 各連結成分についてそこから出る最も重みの小さい辺を見つけ, それらを採用して Union-Find に入れる.

$E_v\ne \varnothing$ であるような頂点のリストを管理しておくことで $O(|V|\log |V|)$ 時間のパートがなくなり, 全体で, $O(|E|/k\cdot \alpha (|V|)\log |V|)$ 時間になる.

計算量

前処理が $O(|E|\log k)$ 時間, ブルーフカ法が $O(|E|/k\cdot \alpha (|V|)\log |V|)$ 時間であるから, $k\in \Theta (\log |V|)$ とすれば合わせて $O(|E|\log \log |V|)$ 時間.

なんかまだ計算量を減らす余地がありそう

はい. $O(|E|\alpha (|E|,|V|))$ 時間になります. その分複雑になっていて実用的ではなさそうですが…

Chazelle, Bernard. "A minimum spanning tree algorithm with inverse-Ackermann type complexity." Journal of the ACM (JACM) 47.6 (2000): 1028-1047.

実装

誰か書いて計測して ♥️
ソートって高速なので, クラスカル法との区別はかなり大変. AVX512 sort とかあるし, ソート部分にかかる時間とソート以外の部分にかかる時間が同じくらいとかなりかねない
リストのリストは遅いから, CSR 形式にして…
少なくとも $|E|\ge 10^7$ は必要かな〜

あした : @H1rono_K さんが書いてくれるらしいです！ :tanosimi-: