高度通信網のためのグラフモデルとアルゴリズムの研究

グラフ理論とグラフの最適化問題は、通信網の性能評価や網設計に基本的なアルゴリズムを与え、大きな貢献をしてきた。近年マルチメディア、マルチサービス網の研究、開発が目指される様になり、通信網は画期的な進歩を成そうとしている。それに伴い従来のグラフ理論では覆いきれない問題が現れる様になってきた。本研究ではそういう新しい要求に応じ、しかも今後普遍的に必要となってくるであろうモデルを構築し、その性質の解明を目指している。

例えばネットワークに同じサービスを供給するデータベースを２つ設置することを考える。図1のネットワークN1は１つの通信リンクの断絶でデータベースにアクセスできないノードが現われる（例えば(c,d)の断絶でd,e,fはa,bにあるデータベースのどちらにもアクセスできない）。しかしネットワークN2は２つ以上の通信リンクが断絶しない限り、どのノードもどちらかのデータベースにはアクセスできる。すなわちN2の方がN1より耐故障性で勝っていると考えられる。

図１

これを理論的に扱うために、グラフG=(V,E) （但しVは節点集合でEは枝集合）に節点部分集合族X={V1, V2, ..., Vp}（ViはVの部分集合で、領域と呼ぶ）を組み合わせた(G,X)を領域グラフ(area graph)というモデルを提案し、各領域間、あるいは各領域と節点間の関係を研究している。例えば図１のネットワークN1, N2はそれぞれ図２の領域グラフ(G, X1={V11={a,b}}), (G, X2={V21={a,e}})で表現される。

図２

そして

(G,X1)の節点・領域連結度(NA連結度; NA-connectivity)は１で、(G,X2)の節点・領域連結度は２である

と言うことができる。少ない設備量で高い節点・領域連結度を達成する問題はマルチメディア網、マルチサービス網の設計、運用には欠かせない問題である。

本研究についてさらに詳しくは、下記の文献を参照されたい。特に文献3は分かりやすい解説記事である。文献1,2は高いNA連結度を保ったまま枝をなるべく多く削除する問題をあつかっている。文献4は最小数の領域内の節点（図１の例で言えばデータベース）を配置することによって所望のNA連結度を得る問題をあつかっている。ここでは枝故障に限定したNA枝連結度に限定している。文献5はNA連結度に加えて節点・領域間の距離も考慮して、それらの良い性質を保ったまま枝をなるべく多く削除する問題について、色々条件の組み合わせを変化させてそれらの性質を明らかにしたものである。文献6は文献4の問題に対し、点故障も考慮した、NA点連結度に関する問題をあつかっている。文献7は文献4の問題に対し、有向グラフ（枝に向きが与えられているグラフ）上で考察したものである。

本研究の主な文献（すみません、ここの文献の更新が間に合っておりません。最新の文献については[発表論文一覧]を御覧下さい。）

  1. 伊藤大雄, "グラフにおける節点・領域連結度について," 電気学会論文誌C, Vol. 114-C, No. 4, pp. 463--469, 1994.
  2. ITO Hiro, "Connectivity problem on area graphs for locally striking disasters --- direct NA-connection," IEICE Transactions, Special section of selected papers from the Karuizawa WS on circuits and systems, Vol. E78-A, No. 3, pp. 363--370, 1995.
  3. 伊藤大雄, "通信網の簡素化問題─連結度、領域グラフ、T-混合カット," NTTR&D, Vol. 44, NO. 4, 1995.
  4. ITO Hiro and YOKOYAMA Mitsuo, "Edge connectivity between nodes and node-subsets," Networks, Vol. 31, No. 3, pp. 157--164, 1998.
  5. MIWA Hiroyoshi and ITO Hiro, "Sparse spanning subgraphs preserving connectivity and distance between vertices and vertex subsets," IEICE Transactions, Vol. E81-A, No. 5, pp. 832--841, 1998.
  6. 伊藤大雄, 伊藤資泰, 上原秀幸, 横山光雄, "節点と節点部分集合間の２および３点連結化問題" 信学技報COMP97-110, 97, pp. 33--40, 1998.
  7. 穂浪昭二, 伊藤大雄, 上原秀幸, 横山光雄, "有向グラフ上の高枝連結節点部分集合生成アルゴリズム," 情報処理学会研究報告（アルゴリズム研究会）, vol. 99, no. 8, pp. 9--16, 1999.

Return to the page of research interests