妨害の下での最短経路問題の複雑さ : 通過後の妨害を許さない場合

スポンサーリンク

概要

論文の詳細を見る
有向グラフG=(V,A)とその2頂点s,t各辺の(正の)重みl(・)が与えられる。2人の競技者P1とP2は、P1がtに着くまで、以下のルールに従って交互に競技を行う。P1は自分の手番毎に1つの辺を辿り、出発地sから目的地tに行こうとする。P2はAから辺を取り除くことによって妨害する。P2が取り除くことのできる辺の総数はKであり、P1が始点を通った辺を取り除くことはできない。P1は通った辺の重みの和が小さくなるようにし、一方、P2は大きくなるようにする。本稿では、2人の競技者が最善を尽くした時の辺の重みの和を、K=1の場合はO(m+nlogn)(m=|A|,n=|V|)時間で求め得ること、K≥2の場合は、全ての辺の重みを1としてもNP-hardであることを示す。
社団法人電子情報通信学会の論文
1995-11-16

著者

関連論文

もっと見る

スポンサーリンク