- 著者
-
永持 仁
石井 利昌
軽野 義行
- 出版者
- 京都大学
- 雑誌
- 基盤研究(C)
- 巻号頁・発行日
- 2002
・最大隣接順序によるグラフ疎化法を利用して,O(n^2(1+min{κ^2,κ√n}/δ))時間,O(n+m)領域の計算量で,点連結度κに対する2倍近似の点カットを計算するアルゴリズムを得た(δはグラフの最小次数).提案するアルゴリズムはδがκと比べて大きい場合には従来よりも高い性能を発揮する.・グラフにソース,シンクと呼ぶ2点s,tが与えられたとき,ソースシンク間の最小(s,t)-カットを求める問題に対しては,有向グラフに対し,無向グラフへの「近さ」を表す指標μを導入し,有向グラフDの最小(s,t)-カットをO(min{m+ν(ν+μ)^<1/2>n,(ν+μ)^<1/6>nm^<2/3>}})時間で計算するアルゴリズムを設計した(νは最小(s,t)-カットの値).この計算量は小さなμを持ちかつ密であるような有向グラフに対しては従来法よりも優れた性能を発揮する.・与えられた単純連結グラフG=(V,E)および2点対の集合Rに対して,何本かの新しい枝をグラフGに付与してRの各2点対間の局所点連結度を2以上にする問題を考える.このとき加える枝の本数を最小にすることが目的である.問題に対する下界の導き方を精密化することで最適な付加枝集合の大きさの高々4/3倍の解を求める線形時間アルゴリズムを設計した.・ネットワーク連結度問題に対する最近の進展についてサーベイを行った.多くのネットワークの連結度問題は最大流最小カットの定理に基づく考察から最大流アルゴリズムを利用したアルゴリズムにより解くことができるが,最近,最大隣接順序と呼ばれる節点の順序付けを利用することで無向ネットワークにおいてはさらに効率の高いアルゴリズムが設計できることが示されている.特に,n,mをネットワークの節点数,枝数としたとき,極値節点集合問題,カクタス表現問題,枝連結度増大問題,供給点配置問題と呼ばれる問題に対してはO(mn+n^2log n)時間のアルゴリズムが設計できることを示す.この計算時間はネットワークの最小カットの値を決定する現在最良の計算量に等しい.これらの多くのアルゴリズムに対して研究代表者により現在最良の計算時間が達成されている.