グラフの連結度増大問題に関する研究

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

グラフの古典的な連結度である辺連結度または点連結度を増大させる問題を中心に,グラフの連結度に関する問題の研究,高速アルゴリズムの開発・実装を行った.まず,任意のh-点連結グラフを,l-辺連結かつk-点連結に同時に増大させる問題に対し,最適値との絶対誤差が0(l(k-h))以内である近似解を多項式時間で求めるアルゴリズムをはじめて構築した.これまで,点連結度のみを増大させる問題でも,最適値との絶対誤差が0(k(k-h))以内の近似解を求めるアルゴリズムが知られている程度だが,本結果は,本質的に異なる概念である辺連結度と点連結度を同時に考慮しても,同等の近似比を得ることに成功したことを示す結果である.また,最近注目されてきている,2点の間ではなく,点と点集合(領域)の間の連結度を表わす概念であるNA連結度に関する問題に対して,次の結果を得た.グラフと領域集合が与えられたとき,全ての点と領域間のNA辺連結度を目標値k以上にする問題に対し,k≧3のとき,多項式時間で解けることをはじめて示した.これまで,この問題に関して,k=1のときNP-困難,k=2のときは多項式時間で解けることが知られていたが,k≧3の場合は,多項式時間で解けるかどうか未解決であった.また,連結度増大問題とは別に,NA連結度に関する問題の1つである供給点配置問題に関して,次の結果を得た.ここで,供給点配置問題とは,各点が要求されたNA連結度を満たすように,領域を配置する問題である.各点が3以下に限定された局所点連結度要求を持つ問題に対し,線形時間アルゴリズムの存在を示した.さらに,4以上の局所点連結度要求を持つ場合は,NP-困難であることも示した.