グラフの連結性に関係するネットワーク設計問題の研究

グラフの連結性は、そのグラフが対応するネットワークなどの繋がり方について考える際に重要である。グラフに木を詰め込む問題はグラフの連結性と強く関係している。本年度の主な成果は到達可能な頂点集合を張る混合木詰め込み問題に関するものである。与えられた有向グラフと根に対して、指定された個数の根付き全域有向木を詰め込むことができるための必要十分条件が Edmonds (1973) によって与えられている。この問題の一般化として、無向グラフと有向グラフの共通の一般化である混合グラフと根が与えられたとき、指定された個数の根付き全域混合木を詰め込むことができるための必要十分条件と実行可能解を求めるか実行可能解が無いことを示す多項式時間アルゴリズムが Frank (1978) によって与えられている。また、別の一般化として、与えられた有向グラフと根の組に対して、それぞれの根から到達可能な頂点集合を張る有向木の組を詰め込むことができるための必要十分条件と実行可能解を求めるか実行可能解が無いことを示す多項式時間アルゴリズムが Kamiyama, Katoh, Takizawa (2009) によって与えられている。本研究では、これらの2つの問題の共通の一般化である、与えられた混合グラフと根の組に対して、それぞれの根から到達可能な頂点集合を張る混合木の組を詰め込むことができるための必要十分条件と実行可能解を求めるか実行可能解が無いことを示す多項式時間アルゴリズムを与えた。本研究は東京大学の谷川眞一氏との共同研究である。なお、この研究に関する論文の、論文誌 Discrete Optimization への採録が決定した。

グラフの連結性は、そのグラフが対応するネットワークなどの繋がり方について考える際に重要である。グラフに木を詰め込む問題はグラフの連結性と強く関係している。本年度の主な成果は到達可能な頂点集合を張る混合木詰め込み問題に関するものである。与えられた有向グラフと根に対して、指定された個数の根付き全域有向木を詰め込むことができるための必要十分条件が Edmonds (1973) によって与えられている。この問題の一般化として、無向グラフと有向グラフの共通の一般化である混合グラフと根が与えられたとき、指定された個数の根付き全域混合木を詰め込むことができるための必要十分条件と実行可能解を求めるか実行可能解が無いことを示す多項式時間アルゴリズムが Frank (1978) によって与えられている。また、別の一般化として、与えられた有向グラフと根の組に対して、それぞれの根から到達可能な頂点集合を張る有向木の組を詰め込むことができるための必要十分条件と実行可能解を求めるか実行可能解が無いことを示す多項式時間アルゴリズムが Kamiyama, Katoh, Takizawa (2009) によって与えられている。本研究では、これらの2つの問題の共通の一般化である、与えられた混合グラフと根の組に対して、それぞれの根から到達可能な頂点集合を張る混合木の組を詰め込むことができるための必要十分条件と実行可能解を求めるか実行可能解が無いことを示す多項式時間アルゴリズムを与えた。本研究は東京大学の谷川眞一氏との共同研究である。なお、この研究に関する論文の、論文誌 Discrete Optimization への採録が決定した。