グラフの多重彩色及び分割に関するアルゴリズム

本研究では,グラフの点に供給点または需要点の役割が与えられ,それぞれに供給量と需要量という重みが与えられた重み付きグラフを扱った.そのようなグラフに対し,需要と供給の条件を満たすようにグラフを分割するアルゴリズムを開発した.まず,木のグラフ分割問題に関してまとめた論文が,学術雑誌に採録された.次に,直並列グラフと呼ばれるグラフのクラスに対し,グラフ分割問題を解くアルゴリズムの開発・解析を行った.グラフ分割問題は木に対してさえNP困難であり,したがって直並列グラフに対し効率のよいアルゴリズムはありそうにない.そこで,本研究では擬多項式時間アルゴリズムの開発を行った.その結果は,2005年5月開催の国際会議にて発表し,現在学術雑誌に投稿中である.また,直並列グラフに対し,より一般的な分割問題を解くアルゴリズムを与えた.この問題では,今まで上限のみ指定することができた連結成分の重みの和の制限を,上限と下限の両方を同時に指定することができるようにした.さらに,グラフの点に複数個の重みが割当てられている場合にも,効率よく解けることを示した.この結果は,現在国際会議に投稿するように準備中である.

本研究では,グラフの点に供給点または需要点の役割が与えられ,それぞれに供給量と需要量という重みが与えられた重み付きグラフを扱った.そのようなグラフに対し,需要と供給の条件を満たすようにグラフを分割するアルゴリズムを開発した.まず,木のグラフ分割問題に関してまとめた論文が,学術雑誌に採録された.次に,直並列グラフと呼ばれるグラフのクラスに対し,グラフ分割問題を解くアルゴリズムの開発・解析を行った.グラフ分割問題は木に対してさえNP困難であり,したがって直並列グラフに対し効率のよいアルゴリズムはありそうにない.そこで,本研究では擬多項式時間アルゴリズムの開発を行った.その結果は,2005年5月開催の国際会議にて発表し,現在学術雑誌に投稿中である.また,直並列グラフに対し,より一般的な分割問題を解くアルゴリズムを与えた.この問題では,今まで上限のみ指定することができた連結成分の重みの和の制限を,上限と下限の両方を同時に指定することができるようにした.さらに,グラフの点に複数個の重みが割当てられている場合にも,効率よく解けることを示した.この結果は,現在国際会議に投稿するように準備中である.