グラフ彩色問題の効率的なアルゴリズム

研究課題

体系的番号	JPMJAX25CT
研究代表者	米田寛峻東京大学, 大学院情報理工学系研究科, 大学院生
研究期間 (年度)	2025 – 2027
概要	計算理論の基盤となる問題のひとつである「グラフ彩色問題」の近似アルゴリズムに関する研究を行う。Kawarabayashi,Thorup,Yoneda(2024)は3彩色可能なグラフを多項式時間でO(n^0.1975)彩色するアルゴリズムを提案したが、この結果を改善することを目指す。それをもとに、3彩色可能なグラフのローカルな特徴やグローバルな特徴を新たに見出す。
研究領域	次世代AIを築く数理・情報科学の革新