組合せ構造を持つ問題を解くアルゴリズムの研究

点击翻译按钮获取中文摘要

本年度の研究実績は大きく3つに分けて述べることができる。1) グラフの連結度(カット、フロー等)に関する種々の問題に対して高速アルゴリズムを開発した。まず,グラフのパス,フロー型の問題に対して,指定された要求を満たすある種のフロー(パスや木)を求める問題に対してにおいて効率の良いアルゴリズムを与えた.ネットワークにおける信頼性問題や表データのセキュリティ問題に現れる連結度増大問題に対し,いくつかの効率の良いアルゴリズムを得た.特に,提案するアルゴリズムによれば辺連結度と点連結度の増大を同時に考慮した新しいタイプの増大問題が多項式時間で解けるようになった。さらに,連結度に関する問題として,連結度を保つ疎なグラフを抽出する並列アルゴリズム,グラフの最小3分割,4分割を行う高速アルゴリズムを設計した.特に,最小3分割アルゴリズムを拡張して対称劣モジュラ集合関数上での3分割問題が効率良く解けることも示した.2) 近似アルゴリズムとしては直線グラフ上の配送車スケジューリング問題に対する1.5倍近似アルゴリズム,最小点被覆問題に対する2-(8m)/(13n^2+8m)倍近似アルゴリズムを与えた(ここで,nは点数,mは辺数).3) アルゴリズムの設計手法の開発を目的として,グラフの連結度問題,協力ゲーム理論に共通する集合関数の理論における研究を行い,「正モジュラ性」という新しい概念を導入し,その基本構造を明らかにした.さらに得られた手法をグラフの連結度増大問題,協力ゲーム理論等へ応用した場合のアルゴリズムについても種々の結果を得た.