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

图的连通性增强问题研究

基本信息

批准号：
13780224
负责人：
石井利昌
金额：
$ 1.34万
依托单位：
Toyohashi University of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

グラフの古典的な連結度である辺連結度または点連結度を増大させる問題を中心に,グラフの連結度に関する問題の研究,高速アルゴリズムの開発・実装を行った.まず,任意の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-困難であることも示した.

我们专注于增加图形的边缘连接或点连接的问题，即经典的图形连接，并开发和实现了高速算法。首先，对于同时增加任意H点连接图的问题，我们已经构建了一种算法，用于找到具有多项式时间为0（l（k-h））的近似解决方案的算法。到目前为止，到目前为止，即使仅增加了点连接的问题，对于找到一个绝对误差为0（k（k-h））的近似解决方案的算法，绝对误差为0（k（k-h）），就仅增加点连接的问题而言，这一点仅增加了点连接，但此结果即使考虑到基本不同的概念，同一概念，相同的近似比率也已成功获得。同样，关于NA连接，这是一个概念，它代表了一个点和点集（区域）之间的连接程度（最近吸引了注意力），这是一个概念，代表了点和点集（区域）之间的连接程度，而不是在两个点之间。对于这个问题，我们获得了以下结果。给定图形和一组区域，我们表明，首次可以在k≧3时使用多项式时间在所有点和区域之间的Na侧连接。过去，众所周知，当k = 1和k = 2时多项式时间时的NP缺陷，但是如果k≧3，则尚未解决是否可以使用多项式时间解决。此外，除了增加连接外，还获得了有关供应点布置问题的结果，这是与NA连接有关的问题之一。在这里，供应点排列问题是每个点满足所请求的NA连接的问题。对于每个点具有本地点连接请求限制为3或以下的问题，显示了线性时间算法的存在。此外，当有4个或以上的本地点连接请求时，还表明需要NP缺乏np-difficulty。