大会名称 |
---|
1996年 総合大会 |
大会コ-ド |
1996G |
開催年 |
1996 |
発行日 |
1996-03-11 |
講演日 |
講演場所(会議室等) |
講演番号 |
3 |
タイトル |
最近の辺連結度アルゴリズムについて |
著者名 |
永持 仁, |
キーワード |
抄録 |
グラフの辺連結度(=カットの最小サイズ)を最大流アルゴリズムを用いずに効率よく計算できることが示されて以来,確率・並列アルゴリズムの開発やすべての最小カット(あるいはそれに準じる小さいカット)を表現するデータ構造の構築などの研究が進んできている.最近では,辺分離というグラフ変形(辺連結度を保ちながら1つ点を除去する操作)をアルゴリズムの高速化が行われた.本稿ではこのような辺連結度問題に関する最近のアルゴリズムの進歩について概説する. |
本文pdf |
PDF download
|