2006.09.05

Research

線形時間で最小全域木を作るだって!?

いまMOCKで一番ネックになりそうなのが、初期化時に全データを含む最小全域木を作るところです。最小全域木の生成アルゴリズムはいくつかあって、データ数(というかリンク数?)Nに対してO(NlogN)で最小全域木を作れるといわれているのだけど、どれも扱うリンクが最初から分かっているという想定なのです。でも実際には各データ間のリンクの重みを求めるのもそれをメモリにのせるのもO(N^2)で大変。特に大規模データではメモリ量が半端じゃない(double型ならN×N×8 [Byte])。データ数に線形なメモリ量で(つまりすべてのデータ間のリンクを考えないで)、高速に最小全域木を作れるアルゴリズムが知りたかった。もしかしたらこの文献はビンゴかもしれない。

A Linear Algorithm for Analysis of Minimum Spanning and Shortest Path Trees of Planar Graphs


Abstract:

We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality...

私訳:
本論では線形時間および線形スペース(おそらくメモリ量のことをいっていると予測)で平面グラフ内のツリーを解析するアルゴリズムを提案する。提案手法はツリーのエッジを置き換えて最小全域木を検出し、それが最小であることを検証する。