「彩色問題」の記事一覧

• グラフ彩色の速度が40年ぶりに大幅向上

  2025-05-13 08:29

  科学・技術

  飛行機の誘導やネットワークの割当などに使われるグラフ彩色問題において、2024年から2025年にかけて複数の研究グループが高速なアルゴリズムを開発。従来40年間ほぼ進展のなかった処理速度を、ほぼ理論限界とされる線形時間近くにまで短縮しました。鍵となったのは「プライミング」と呼ばれる戦略で、あらかじめグラフ構造を塗りやすい形に変換することで効率を飛躍的に高めています。今後の応用や定数削減にも期待が集まっています。