ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	日本語
発行・発表の年月	1996/11/25
形態種別	国内学会誌（First author）
査読	査読あり
標題	妨害者のいる場合の最短経路問題
執筆形態	共著・編著（代表編著を除く）
掲載誌名	電子情報通信学会論文誌. A, 基礎・境界
出版社・発行元	一般社団法人電子情報通信学会
巻・号・頁	79(11),1866-1876頁
担当区分	筆頭著者
著者・共著者	山口 一章,荒木 俊郎,柏原 敏伸
概要	出発地,目的地なる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であることを示す.
ISSN	0913-5707
NAID	110003312548
PermalinkURL	http://id.ndl.go.jp/bib/4086569