大域的分散グラフアルゴリズムに対するパラメタライズド手法の確立

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

複数の計算機が通信リンクで相互接続した分散システムにおいて、ネットワークのトポロジカルな構造に立脚した何らかの組み合わせ最適化問題(最短経路問題、彩色問題等)をネットワーク自身が計算したいという要求は自然な問題設定であり、また多くの応用が存在する。分散グラフアルゴリズムとは、複数の計算機が通信リンクで相互接続した分散システムにおいて、ネットワークのトポロジカルな構造を入力データと見なしてグラフアルゴリズムを実行する枠組みである。本研究では、グラフ理論の基本的な諸問題のうち、特に求解のために大域的な情報収集を必要とする問題(大域的な問題)を対象とし、入力インスタンスの困難性に応じた最適な計算時間を達成する分散グラフアルゴリズムをパラメタライズドアルゴリズムの文脈から模索し，以下に示すような成果を得た．令和4年度に関しては，主に既に得られていた知見を研究論文として刊行する，ならびに採択が決定した論文を国際会議にて発表することが主な作業であったが，昨年度に得られていた以下の2成果についてそれぞれ国際会議における発表，論文刊行を行った．(1)木幅制限グラフに対する効率的な分散グラフアルゴリズムの統一的設計手法の提案(2)最大マッチング問題に対する高速なパラメタライズド分散アルゴリズムの発見また，本研究に関連する以下の追加的な成果を得ることができた．(3)最短経路の最致命辺問題に対するパラメータ可複雑性の精緻な解析