- 著者
- 永持 仁 岩田 健吾 石井 利昌
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. 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|以下の整数だけでよく,実装における問題点を解決することができる。
1 0 0 0 離散原像問題の解析と応用
今年度は以下の研究を行った。(1) ニューラルネットワークについての原像問題に取り組み、学習した階層型ニューラルネットワークに対し、出力ベクトルから入力ベクトルを求める問題を混合整数線形問題(MILP)として定式化し、MILPソルバーを用いて入力ベクトルを計算する手法を開発した。この手法を実装し、Core i5 1.8GHz CPU上でCPLEXソルバーを用いた予備的な計算機実験を行った結果、入力層が200頂点、中間層(一層)が200頂点、出力層が1頂点の場合に2秒以内で計算結果を得ることができた。(2) ニューラルネットワークの応用面についても研究を行い、遺伝子発現データと他の情報を統合して解析するための2種類の手法を開発した。一つは遺伝子発現データとタンパク質相互作用ネットワークデータを統合して解析する手法であり、タンパク質相互作用ネットワークデータをグラフらプラシアンを用いて2次元点集合に変換し、遺伝子発現データを対応する点の強度とすることにより、各サンプルのデータを画像データとして扱えるようにし、それに対し深層学習による画像解析技法を適用することにより腫瘍細胞の分類を行う。もう一つは遺伝子発現データと遺伝子間の進化的距離を統合して解析する手法であり、進化的距離データに多次元尺度構成法を適用することにより各遺伝子を2次元点集合に変換し、前者と同様の手法を適用することにより、腫瘍細胞のサブタイプの分類を行う。いずれも公開データから取得した遺伝子発現データを用いた計算機実験により、その有用性を示した。(3) 木構造に対する離散原像問題に取り組む事前研究として、無順序木の包含問題(Unordered Tree Inclusion)問題の計算量改善に取り組み、最大次数に関する指数時間依存性を改良することに成功した。
1 0 0 0 OA グラフの連結度増大問題
- 著者
- 永持 仁
- 出版者
- 一般社団法人日本応用数理学会
- 雑誌
- 応用数理 (ISSN:09172270)
- 巻号頁・発行日
- vol.8, no.1, pp.20-29, 1998-03-16
The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem is first studied by K. P. Eswaran and R. E. Tarjan in 1976, and both type of connectivity augmentation problems for k=2 are shown to be polynomially solvable. Afterwards, in 1987 T. Watanabe and A. Nakamura proved that the problem of making a given graph k-edge-connected by adding the smallest number of edges can be solved in O(k^2(kn+m)n^4) time for general k, where n and m are the number of vertices and edges in the input graph, respectively. Recently, a significantly faster O(nm log n+n^2 log^2 n) time algorithm for solving this problem is proposed by H. Nagamochi and T. Ibaraki by applying L. Lovasz's edge-splitting theorem. This note first reviews this alogorithm and then shows how to modify the algorithm to solve the edgeconnectivity augmentation problem for a graph with real-weighted edges.
・最大隣接順序によるグラフ疎化法を利用して,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)時間のアルゴリズムが設計できることを示す.この計算時間はネットワークの最小カットの値を決定する現在最良の計算量に等しい.これらの多くのアルゴリズムに対して研究代表者により現在最良の計算時間が達成されている.
1 0 0 0 グラフ・ネットワーク問題を解くアルゴリズムの研究
本研究ではグラフ構造の解明,高速グラフアルゴリズムの開発を行った.グラフの連結性に関する問題について以下の結果を得た.重み付き無向グラフのすべての最小カットを,カクタスと呼ばれるグラフ構造に表現するアルゴリズムの計算量を軽減した.ここで使われている手法は最大隣接順序というグラフの探索法であり,すべての最小カットを計算するために最大流アルゴリズムを必要としない点が特徴である.グラフを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<>は調和関数).
1 0 0 0 最近のアルゴリズムから
- 著者
- 永持 仁
- 出版者
- 公益社団法人日本オペレーションズ・リサーチ学会
- 雑誌
- オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch (ISSN:00303674)
- 巻号頁・発行日
- vol.40, no.1, pp.36-37, 1995-01-01