通信スケジューリングのグラフアルゴリズムによる解法

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

今年度は効率のよい通信スケジューリングのアルゴリズムをグラフアルゴリズム、特にリスト辺彩色や多重彩色アルゴリズムを応用して研究開発を行なった。リスト辺彩色や多重彩色問題は辺彩色や点彩色問題の一般化であり、NP-困難である。一般のグラフに対してはこの問題を解く効率の良いアルゴリズムが存在しないと予想されている。我々はグラフのクラスを限定したとき、即ち直並列グラフや部分k木に対して効率よいアルゴリズムを開発成功した。それらの成果を以下の論文でまとめた。1.Tomoya Fujino, Shuji Isobe, Xiao Zhou, and Takao Nishizaki Linear algorithm for finding list edge-colorings of series-parallel graphs IEICE Trans. on Information and Systems, E86-D(2003), pp.186-1902.Takehiro Ito, Takao Nishizaki, Xiao Zhou Algorithms for multicolorings of partial K-trees IEICE Trans. on Information and Systems, E86-D(2003), pp.191-200また、限定されたグラフに対して効率よいアルゴリズムや一般グラフに対して近似アルゴリズムや確率的アルゴリズム等の調査も行った。現在知られているアルゴリズムの理論的評価および計算機による実験的シミュレーションを行い、各手法によって得られるデータを分析した。また各手法の効率を理論と実験両方で検証した。