情報処理学会 第81回全国大会講演要旨

グラフ上のパケットルーティング問題とは，通信ネットワークをモデル化したグラフと，パケットの集合が与えられた際に，制約時間内に受信先ノードに到達するパケットの数を最大化するスケジューリングを求める問題である．本問題はグラフをパスに限定した場合ですらNP困難であることが知られ，オンラインアルゴリズムや近似アルゴリズム等の観点から様々な研究が行われてきた．本研究では，この問題に対してパラメータ複雑性の観点から研究を行った．特に，「パケット数」や「最大締切時刻」がそれぞれ単独で小さい場合にはW[1]困難であることを示した一方で，それらの両方が小さければパラメータ容易であることを示した．