「静的ネットワークにおける周波数割当て問題に対する近似アルゴリズム」

藤重研究室　久家　貴広

携帯電話などの移動通信体に用いられるセルラーネットワークでは，個々の通信

に対し，干渉を起こさないように周波数帯域を効率的に割当てることが重要な問

題になる．セルラーネットワークは三角形で構成される無限格子の部分グラフ

-hexagon グラフ-としてモデル化される．あらかじめ各基地局で必要とされ

る通話数がわかっている静的な状況では，周波数割当てをhexagon グラフの多重彩

色問題に帰着することができる．

この問題は２部グラフおよびサイクルに限定した場合は最小色数による線形時間

の彩色アルゴリズムが提案されているものの，一般にはNP-困難であることが知

られている．既知の最良の近似アルゴリズムは

Narayanan--ShendeやMcDiarmid--Reedのもので，

どちらも必要とされる最小色数に対し，約３分の４倍の色数による

彩色を与える．

論文では，hexagon グラフの多重彩色問題に関する研究結果を報告する．ま

ず計算機実験により諸近似アルゴリズムの性能を比較考察する．前述の2つの近

似アルゴリズムに加え，greedyな方法による彩色と，McDiarmid--Reedのものを

簡素化した彩色アルゴリズムを評価対象とした．

また，最大クリーク数が２のhexagon グラフに対する新たな近似アルゴリズムを

提案する．対象となるグラフは限定されるものの，必要とされる色数は

約４分の５倍の色数となり既知のものより改良されている．