グラフ分割アルゴリズムの新しい設計手法に関する研究

点击翻译按钮获取中文摘要

本年度は,主に選挙区割問題などに応用がある「グラフの均一分割問題」について研究を行った.この問題は,点に整数の重みが付いたグラフが与えられたとき,グラフから辺を削除し,各連結成分に含まれる点の重みの合計が均一になるように分割する問題である.本研究では,各点に2つ以上の重みが与えられていても,部分k木の均一分割問題が擬多項式時間で解けることを示した.また,2つ以上与えられた点の重みのうち,分割を求める際には1つだけを自由に選択できる場合についても考察を行い,擬多項式時間アルゴリズムを与えることができた.これらの結果は,IEICE Trans.on Information and Systemsに掲載になった.また,電力系統の配電融通問題などに応用がある「需要点と供給点のあるグラフの分割問題」も研究を進めた.この問題は,需要点と供給点のあるグラフに対し,電力が供給されない需要点ができてしまうとき,供給されている需要点の需要量の合計を最大にする最大化問題である.この問題の近似可能性を明らかにした論文を,海外の学術雑誌に投稿した.