妨害の下での最短経路問題の複雑さ

• Item type: SIG Technical Reports(1)
• 公開日: 1995-03-09
• タイトル: 妨害の下での最短経路問題の複雑さ
• タイトル / 言語: en
• タイトル: The complexity of shortest path problem under obstruction
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学
• 著者所属: 大阪大学
• 著者所属: 大阪大学
• 著者所属(英): en
• 著者所属(英): Osaka University
• 著者所属(英): en
• 著者所属(英): Osaka University
• 著者所属(英): en
• 著者所属(英): Osaka University
• 著者名: 山口, 一章; 荒木, 俊郎; 柏原, 敏伸
• 著者名(英): Yamaguchi, Kazuaki; Araki, Toshiro; Kashiwabara, Toshinobu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 有向グラフG=（，）と妨害数なる正整数K，各辺の重み（正）が与えられている．プレイヤー1は出発地点から，1回に1つの辺をたどって目標地点まで行く．プレイヤー2は自分の手番にいくつかの辺を切断する．プレイヤー2の切断できる辺の数はゲームを通じてK本までとする．プレイヤー1は道のりができるだけ小さくなるようにし，プレイヤー2はできるだけ大きくなるようにする．本稿では，2人が最善を尽くしたときの道のりをO（^K（+nlo)）（=|A|，n=|V|）時間で求め得ることと，全ての辺の長さが1であるとしても，道のりを求める問題がP?SPACE?completeであることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let G = (V,A) be a directed graph with (positive) arc-length, and an integer K is specified. Player1 attempts to move from starting point to destination, moving along one arc during each turn. Player2 deletes arcs from A during his turn. The number of arcs which Player2 can delete within a game is K. Player1 tries to keep the path length to a minimum value, while Player2 attempts to make it as large as possible. What value will it be? In this paper, we show that the problem can be solved in O(n^K(m + nlogn)) time (m = |A|,n = |V|), and that it is P-SPACE-complete even if every arc-length is 1.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1995, 号 26(1994-PRO-021), p. 169-176, 発行日 1995-03-09
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会