妨害者のいる場合の最短経路問題

概要

論文の詳細を見る
出発地,目的地なる2頂点s,tが指定されたグラフG=(V,E),妨害数なる正整数k,各辺の(正の)重みl(・)が与えられている.このとき,2人の競技者P1とP2が以下のルールに従ってゲームを行う. P1はsを出発地点とし,1回に一つの辺をたどって目標地点tまで行こうとする.P2は自分の手番にいくつかの辺を切断する.P2の切断できる辺の数はゲームを通じてk本までとする. P1, P2ともグラフ全体が見えているものとする.P1は自分の通る辺の長さの和(道のり)ができるだけ小さくなるようにし,P2はできるだけ大きくなるようにする.本論文では,2人が最善を尽くしたときの道のりをO(n^<k-1>(m+nlogn)) (m=|E|, n=|V|)時間で求め得ることを示す.また,2人が最善を尽くしたときの道のりが与えられたある正整数以下であるか否かを判定する問題はすべての辺の長さを1とした場合でもP-SPACE-completeであることを示す.
社団法人電子情報通信学会の論文
1996-11-25