本論文は多重彩色問題およびチャネル割当問題の近似解法について記したものである．多重彩色問題およびチャネル割当問題はいずれも頂点彩色問題を特殊な場合として含む問題である．本研究の主な成果をモデルの観点から述べる．多重彩色問題に関しては，入力グラフを限定した場合にのみ，近似解法が知られていた．本研究では，入力グラフとしてより広いグラフクラスを扱い，近似解法を提案した．チャネル割当問題に関しては自明でない近似解法は知られていなかった．本研究では，実務において現実的と思われる仮定を入力グラフに与えた場合の（自明でない）近似解法を提案した．本研究の主な成果を解法の観点から述べる．本研究ではパーフェクトグラフに着目し，パーフェクトとは限らないグラフを入力とした多重彩色問題に対する効率的な解法を提案した．この解法は，格子状グラフを入力グラフとした場合には多項式時間近似解法であり，良い近似率を達成する．チャネル割当問題に対しては，パーフェクトグラフを入力とした場合の近似解法を提案し，それを基に，より広いグラフクラスの近似解法を提案した．「パーフェクトグラフを，パーフェクトとは限らないグラフの近似解法に利用する」という手法は，本研究の大きな特徴といえる．本研究では，問題の入力グラフとして，格子状グラフおよび単位円グラフを扱っている．これらのグラフは，現実のチャネル割当問題において多く現れるグラフであり，有名なベンチマーク問題であるPhiladelphia問題例の入力グラフを含む．

多重彩色問題に関する成果を以下に簡単にまとめる．本研究で提案した解法は，入力グラフが三角格子グラフの場合，その近似率がほぼ4/3の多項式時間近似解法となる．この近似率は，得られる彩色の上界の見積もりに関する定数項を除けば，既存の最良の近似率と同じである．三角格子グラフの多重彩色問題に対して，近似率が4/3より小さい多項式時間近似解法があるならばP=NPとなることが，既存の結果からわかっている．本研究で提案した多項式時間近似解法は，入力グラフが三角格子点上の単位円グラフの場合，四角格子点上の単位円グラフの場合，三角格子グラフのk乗グラフの場合，入力グラフが四角格子グラフのk乗グラフの場合には多項式時間近似解法となる．各グラフに対する近似率は，各グラフがパーフェクトである条件を整理した定理により導かれる．その定理により，各グラフの最大重み安定集合問題の近似解法，各グラフの有理彩色数の見積もり，各グラフの非パーフェクト率の見積もりなども得られた．一方，対角格子グラフの多重彩色問題がNP-困難であることも示した．

最小スパンチャネル割当問題に関する成果を以下に簡単にまとめる．入力グラフの枝の重みが全て同じチャネル割当問題を解く多項式時間近似解法を提案した．その解法は，入力グラフがパーフェクトグラフグラフまたは単位円グラフの場合にはO（log n）-近似解法になる，ここでnは入力グラフの頂点数である．また，この解法を基に，一般のグラフに対するO（n）-近似解法も提案した．これらの解法の基となるアイディアは，枝の重みが全て同じとは限らない問題クラスに対しても適用可能である．その例としてPhiladelphiaの問題例を含む問題クラスを定義し，その近似解法も示した．また，入力グラフが単位円グラフで，枝の重みに現実的な仮定が与えられた場合の近似解法を提案した．

最適化問題は，限られた資源を効率的に利用するための重要な数理手法である．またその適用先は，機器の進歩や社会的な要請の変化に応じて，様々な分野に出現する．各種の実務的な場面に現れる最適化問題は離散的な構造を含むことが多く，その許容解の数は，組合せ的に増大する非常に大きな数となることが通常である．組合せ的構造を持つ最適化問題については，数学的構造を元に性能の良いアルゴリズムを個別に設計する必要があり，そのためには問題の数学的構造の解明を最適化の観点から行なう必要がある．

本研究で扱う2つの問題は，携帯電話ネットワーク等の周波数割当問題という工学的背景を持っており，1970年代より研究されているものである．しかしながら，近年の携帯電話に代表される情報機器の発達により，問題の重要性は以前とは比べものにならないほど増している．更に周波数割当問題を解く場面は，地球規模のネットワークの設計や，災害時の緊急無線網の設営等，様々な状況が出現している．このような時代の要請から，状況毎に異なる要求に応える，様々なアルゴリズムを導く枠組みを構築する必要がある．

本論文は「多重彩色問題とチャネル割当問題の近似解法」と題し，多重彩色問題とチャネル割当問題に対する近似解法の枠組みを提案し，種々のグラフクラスに適用した際の理論的な近似精度を与えるものである．取り扱っている2つの問題は，携帯電話ネットワークや災害時の緊急無線網等における基地局への周波数割り当ての際，実際に扱われる問題である．本論文で提案する解法に共通する特徴は，パーフェクトグラフと呼ばれるグラフクラスの特徴を積極的に用いている事である．実務上の周波数割当問題に出現するグラフは，パーフェクトグラフではなく，その解法を直接適用する事は困難であるが，2次元平面の格子点を頂点とするという特殊性を持つ場合が多い．本研究では，格子点上に定義されるグラフをパーフェクトグラフに分解し，分割統治法を適用するという解法の枠組みを提案している．この枠組みは，三角格子あるいは四角格子上に定義される様々なグラフクラス等に適用可能である．本論文は，第1章「はじめに」，第5章「まとめと考察」を含め，5章より成る．

第1章「はじめに」では，本研究の目的，関連する先行研究について論じている．特に本研究において扱う2つの問題が，周波数割当問題に端を発する工学的な背景を持つ事を明らかにし，その経緯から格子状グラフ及び単位円グラフと呼ばれるグラフクラスを対象とする事の妥当性を論じている．

第2章では，本論文で扱う数学的な概念，用語，記号を定義している．

第3章「格子状グラフの多重彩色問題」では，三角格子及び四角格子上に定義されるグラフに対する多重彩色問題に対する近似解法の枠組みを提案している．提案される解法のアイデアの根幹を成すものは，格子状グラフのパーフェクトグラフへの分解手法である．本論文では，三角格子状のグラフがパーフェクトグラフとなる必要十分条件を導き，この構造を積極的に利用して多重彩色問題を解く近似解法の枠組みを提案している．この結果は他の格子状グラフクラスについても拡張可能であり，その例として四角格子状のグラフへ適用した際の議論を行ない，同様にして近似解法が構築できることを示し，その近似精度を示している．更にこの定理を援用することで，格子状グラフ上に定義される最大安定集合問題に対する近似解法の提案も行っている．また，格子状グラフ上に定義される有理彩色問題の解法を提案し，これを用いて格子状グラフの非パーフェクト率を算定している．

第4章「チャネル割当問題」では，チャネル割当問題の近似解法の枠組みを提案している．提案する解法の枠組みは，パーフェクトグラフ，単位円グラフ等のグラフクラスに適用可能である．また一般のグラフに適用した場合の近似精度についても考察を行なっている．解法は，グラフの最大クリーク問題の解を利用してグラフを分割し，分割して得られた個々のグラフに対し近似彩色法で得られた解を元にチャネルの割り当てを行なうものである．本研究で対象としている問題は，枝重みが一定の場合のチャネル割当問題であるが，解法のアイデアは，枝重みが枝によって異なる問題へも拡張可能である．しかしながら，その場合の解法は枝重みに強く依存したものであり，近似比率の算定には個別の議論が必要となる．本研究では，歴史的に重要なフィラデルフィア問題例について，枝重みが異なる場合のアルゴリズムを構築し，近似比率の算定を行なっている．

以上を総合するに，本論文は，工学的な背景を持つ多重彩色問題およびチャネル割当問題に対する解法の新たな枠組みを提案することにより，周波数チャネルという限られた資源の有効利用のための数理的手段を提供しており，数理工学の分野の発展に大きく寄与するものである．

よって本論文は，博士 （情報理工学） の学位請求論文として合格と認められる．