このプログラムは、ハイパーグラフの極小横断を列挙するアルゴリズム [Tamaki 2000] を実装したものです。 ハイパーグラフHの横断とは、 Hに属す集合のすべてと空でない交わりを持つ集合を言う。 Hの極小横断とは、Hの横断で、 そのどの真部分集合もHの横断ではないようなものを言う。
このアルゴリズムは、Fredman と Khachiyan のアルゴリズムの変形で、 n を入力ハイパーグラフの大きさ、m を極小横断の個数としたとき、 実行時間は Fredman と Khachiyan ほぼ同じ (n + m)^{O(log n)}ですが、 使用メモリが O(n log n) ワードで済むという特徴を持っています。 ただし、この実装では、アルゴリズムに完全に忠実でないため、 このメモリ量の理論的上限が保証されていません。 それでも、出力の個数が膨大なときでも、 少ないメモリ量で実行できることが観察できます。
玉木 久夫(明治大学)
このデモは 明治大学 玉木久夫 教授 のプログラムを利用しています。