グラフ上の拡散競争ゲームの計算複雑さ
スポンサーリンク
概要
- 論文の詳細を見る
グラフ上の拡散競争ゲームは,社会ネットワーク上における情報の拡散をモデル化したゲームとして提案された多人数ゲームである.本論文では,無向グラフG=(V,E),整数の点重み関数w:V→Z,プレイヤー人数kが入力として与えられた時に,点重み関数wを持つグラフG上のk人拡散競争ゲームにナッシュ均衡が存在するか判定する問題について解析を行った.その結果,一般グラフの場合は,点重みが全て1の場合ですらNP完全であることを示し,さらに点重みが整数の場合は,入力グラフが2つの連結成分からなる森の場合ですらNP完全であることを示した.
- 2012-03-09
著者
-
周 暁
東北大学大学院情報科学研究科
-
伊藤 健洋
東北大学大学院情報科学研究科
-
内沢 啓
東北大学大学院情報科学研究科
-
内澤 啓
農林水産省構造改善局計画部資源課
-
内澤 啓
東北大学大学院情報科学研究科
-
伊藤 健洋
東北大学情報科学研究科
-
佐藤 永幸
東北大学大学院情報科学研究科
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- バランスのよいグラフ分割を用いた平面グラフの小面積格子描画法
- リスト辺彩色の再構成問題
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 木の均一分割問題
- 3連結平面グラフの細分の格子凸描画
- 需要点と供給点があるグラフの分割問題の近似可能性
- 直並列グラフの折れ曲がり最小の直交描画
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 再構成問題の計算複雑さ
- 需要と供給の木の分割
- Efficient Algorithms for Edge-Coloring Partial k-Trees
- 部分k-木で辺素な道をみつけるアルゴリズム
- 部分k木を全彩色する多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 農業における自然エネルギの利用
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- しきい値回路のパターン数について (理論計算機科学の深化 : 新たな計算世界観を求めて)
- エネルギー計算量に制限のある定数段しきい値論理回路のサイズの指数下界について
- An Energy Complexity Measure for Threshold Circuits that is Motivated by Biological Data on Cortical Computations (Theoretical Computer Science and its Applications)
- しきい値論理回路のエネルギー計算量
- しきい値論理回路のエネルギー計算量
- A-026 グラフ分割を用いた格子描画法(モデル・アルゴリズム・プログラミング,一般論文)
- グラフの距離辺彩色アルゴリズム
- Reconfiguration of list edge-colorings in a tree (コンピュテーション)
- 需要点と供給点のある木のコスト最小分割
- 部分k木で辺素な道を見つけるアルゴリズム
- 木を辺ランク付けする効率のよいアルゴリズム
- 部分k木を[g,f]-辺彩色する多項式時間アルゴリズム
- 部分k-木に対する[g,f]-辺彩色アルゴリズム
- 部分κ木を辺彩色する並列アルゴリズム
- 部分$k$木を全彩色する線形時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)
- DS-1-4 剰余関数を計算するしきい値回路のエネルギー複雑度とファンイン(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- エネルギー複雑度を用いた線形決定木の下界導出
- 部分集合和遷移問題の多項式時間近似スキーム
- LA-11 直並列グラフをリスト辺彩色するアルゴリズム(A. アルゴリズム・基礎)
- 直並列グラフをリスト辺彩色するアルゴリズム
- 部分k-木のl-点彩色多項式時間アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 木のリスト辺彩色の遷移可能性
- A-37 直並列グラフのリスト全彩色(グラフアルゴリズム(1),A.アルゴリズム・基礎)
- Lower bounds for linear decision trees via an energy complexity argument (コンピュテーション)
- 剰余関数を計算するエネルギー複雑度の小さいしきい値回路
- 退化的グラフの全彩色
- 部分k-木の全彩色を求める線形時間アルゴリズム
- 部分k-木の全彩色を求める多項式時間アルゴリズム
- 部分κ-木の一般化点ランキング
- 木の一般化辺ランキング
- 木の分割問題を解くアルゴリズム
- 直並列グラフの重み付き彩色の効率のよいアルゴリズム
- 部分k木で独立全域木を見つけるアルゴリズム
- 部分κ木に対する辺素な道問題のNP-完全性
- 部分k-木をf-辺彩色するアルゴリズム
- グラフの辺彩色及びƒ-辺彩色アルゴリズム
- 部分集合和遷移問題の多項式時間近似スキーム
- エネルギー複雑度を用いた線形決定木の下界導出
- 木,カクタスにおける点被覆の遷移可能性 (コンピュテーション)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 木,カクタスにおける点被覆の遷移可能性
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- DS-1-5 ひとりにしてくれ数(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-9 グラフのL(2,1)ラベリングの遷移可能性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- グラフ上の拡散競争ゲームの計算複雑さ
- 論理回路の出力パターン数え上げ
- グラフの帯域幅連続多重彩色を求めるアルゴリズム
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- 関数$P^n_D$を計算するしきい値回路 (理論計算機科学の新展開)
- Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimensional Arrays (New Trends in Theoretical Computer Science)
- トロミノ詰込問題の計算複雑さについて
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- 論理回路の出力パターン数え上げ(一般)
- 次数指定した最大正則誘導部分グラフ探索問題(一般)