著者

永持 仁 岩田 健吾 石井 利昌

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.31, pp.31-38, 2003-04-18

---

本研究では,グラフG= (V, E)と2つの素な節点集合(資源節点集合)T_1,T_2⊊V(|T_1|,|T_2| : 偶数)が与えられたとき,次の(i),(ii)を満たす節点集合の2分割{V_1,V_2}を見つける問題を考える。(i) |V_1∩T_j|=|V_2∩T_j|=|T_j|/2,j=1, 2, (ii) V_1とV_2が誘導するGのグラフはともに連結。この資源集合の均等問題はNP-困難であるが,入力グラフGが3点連結グラフならば,必ず(i),(iii)を満たすVの分割が存在し,そのような分割がO(|V|^2log|V|)時間,O(|V|+|E|)領域で求められることが知られている。このアルゴリズムでは,いったん入力グラフGを,凸埋め込みと呼ばれる配置として平面上に埋め込み,その埋め込みに対し,資源節点集合を均等分割するハムサンドイッチカット定理を適用することで,Vの分割を求めている。しかし,計算機上で実装する場合には,グラフの節点に対し実際に平面上の点座標を計算,格納することに伴う計算誤差のために,節点数の多い問題に対しては計算が破綻する恐れがある。本研究では,まず,凸埋め込みの方法について,従来法よりも簡単に節点の配置場所を計算する方法を提案し,次に,各節点の座標を実際に計算する代わりに,各節点間の相対位置関係に基づいたデータ保持方法を提案する。新しいアルゴリズムはO (|V|^2)時間,O (|V|^2)領域でグラフの分割を求める。実行中に各セルの保持する数値は大きさ|V|以下の整数だけでよく,実装における問題点を解決することができる。

著者

石井 利昌 前田 壽哉 安彦 篤 福田 六花 山田 恭司 高木 正之

雑誌

日本臨床外科学会雑誌 = The journal of the Japan Surgical Association (ISSN:13452843)

巻号頁・発行日

vol.62, no.1, pp.244-248, 2001-01-25

被引用文献数

3

著者

永持 仁 石井 利昌 軽野 義行

出版者

京都大学

雑誌

基盤研究(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)時間のアルゴリズムが設計できることを示す.この計算時間はネットワークの最小カットの値を決定する現在最良の計算量に等しい.これらの多くのアルゴリズムに対して研究代表者により現在最良の計算時間が達成されている.

著者

永持 仁 石井 利昌

出版者

豊橋技術科学大学

雑誌

特定領域研究(B)

巻号頁・発行日

1998

---

本研究ではグラフ構造の解明,高速グラフアルゴリズムの開発を行った.グラフの連結性に関する問題について以下の結果を得た.重み付き無向グラフのすべての最小カットを,カクタスと呼ばれるグラフ構造に表現するアルゴリズムの計算量を軽減した.ここで使われている手法は最大隣接順序というグラフの探索法であり,すべての最小カットを計算するために最大流アルゴリズムを必要としない点が特徴である.グラフをk-分割する枝集合はk-カットと呼ばれる.最小k-カットを求める問題に対し,グラフの2-カットを大きさの小さい順に部分的に列挙するという新しいアプローチにより,k=3,4,5,6に対して従来の計算量を改善した.k-辺連結でないグラフにおいて,カット値がk未満のカットから適当なものをいくつか互いに交叉しないように選んでやると,グラフの連結度増大問題を解くために必要な情報が取り出せるという性質を示した.あらかじめこのようなカットの集合を求めておけば,連結度増大問題における解の形を細かく制御できることを示した.近似解を求めるアルゴリズムについて以下の結果を得た.グラフの点連結度増大問題は,これまで,目標の点連結度kに対し,入力のグラフの点連結度が(k-1)である場合にしか解法が知られていなかったが,新たに,入力グラフの連結度が任意である場合のアルゴリズムを与えた.このアルゴリズムは最適解に比べ,高々2(k-α)k本しか余分に付加辺を使わない解を計算する(ここでα=(入力グラフの点連結度)).さらに連結度増大問題では点連結度と辺連結度を同時に扱うものも研究し,目標値のみに依存する絶対誤差の近似アルゴリズムを得た.この他,相対誤差のアルゴリズムとして,重み付き3点連結化問題に対する(7/2)-近似アルゴリズム,最小重み辺支配集合問題に対する2-近似アルゴリズム,次数dのハイパーグラフ上のネットワーク設計問題に対するdH(r)-近似アルゴリズムを設計した(rは連結度の最大要求量,H<>は調和関数).