| 開催日時： 2022年7月28日 (木) 13:00 ～ 15:00 開催場所： ズーム 参加対象者： 研究代表者・研究分担者・研究協力者・その他関係者 概要： 効用関数付きグラフ最適化問題とは，グラフ上で定義されるゲーム理論の枠組みを取り入れた問題である．最も代表的なものとして，グラフヘドニックゲームが挙げられる．グラフヘドニックゲームは重み付きグラフ上で定義される．頂点は人，辺重みは友好度を表し，各人の効用は隣接頂点の友好度（すなわち辺重み）の関数で定義される．グラフヘドニックゲームの目的は，最大総効用分割や安定分割などの望ましい性質を満たすグラフ分割を求めることである．近年では，グラフヘドニックゲームの亜種も数多く提案されている．本発表では，これらの効用関数付きグラフ最適化問題の計算複雑性やパラメータ化計算量とその周辺の話題について紹介する． |
参加申込