文献

J-GLOBAL ID：202202276240143435   整理番号：22A1045780

マルチレベル臨界ノード問題の計算量【JST・京大機械翻訳】

Complexity of the multilevel critical node problem

著者 (3件)： Nabli Adel (CIRRELT and Departement d’Informatique et de Recherche Operationnelle, Universite de Montreal, Montreal, QC, Canada) ,  Carvalho Margarida (CIRRELT and Departement d’Informatique et de Recherche Operationnelle, Universite de Montreal, Montreal, QC, Canada) ,  Hosteins Pierre (COSYS-ESTAS, Universite Gustave Eiffel, Villeneuve d’Ascq, France)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 127  ページ： 122-145  発行年： 2022年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本研究では,マルチレベル臨界ノード問題(MCN)と呼ばれるグラフで演じた逐次ゲームを解析した。防御者と攻撃者はこのゲームのプレーヤーである。防御者は,攻撃から頂点(ワクチン接種)を予防して開始する。次に,攻撃者は,非接種頂点の部分集合に感染し,最終的に,防衛者は保護戦略と反応する。MCNとそのサブゲームに関連した最初の計算量結果を提供した。さらに,ユニタリー,加重,無向および有向グラフを考慮することにより,これらの問題の理論的な扱いやすさがどのように変化するかを明らかにした。著者らの知見は,新しいNP完全,Σ2p完全およびΣ3p完全問題に寄与する。さらに,ゲームの最終レベルに対して,保護段階,あるグラフクラスに対する多項式時間アルゴリズムを構築した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  グラフ ,  多項式 ,  ゲーム ,  有向グラフ ,  戦略 ,  *臨界 ,  *計算量 ,  予防接種 ,  問題 ,  頂点
準シソーラス用語： *マルチレベル ,  プレイヤ ,  多項式時間アルゴリズム ,  NP完全性 ,  攻撃者 , 【Automatic Indexing@JST】

著者キーワード (4件)： 三レベルプログラミング ,  デフェンダー・アタッカー・デフェンダー ,  臨界ノード問題 ,  多項式階層

分類 (1件)： ゲーム理論  (KA03060T)

タイトルに関連する用語 (5件)： マルチレベル ,  臨界 ,  ノード ,  問題 ,  計算量