文献

J-GLOBAL ID：202302236688278995   整理番号：23A1829666

疎グラフに対するアルゴリズム的メタ定理

Algorithmic Meta Theorems for Sparse Graphs: A Survey

著者 (1件)： 小林靖明 (京大)
資料名： RAMP数理最適化シンポジウム論文集  (Proceedings of the RAMP Mathematical Optimization Symposium)
巻： 33rd  ページ： 111-131  発行年： 2021年11月18日 
JST資料番号： Y0030B  ISSN： 2435-2438  資料種別： 会議録 (C)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,疎なグラフに対するアルゴリズムメタ定理を紹介する.本稿で扱うアルゴリズム的メタ定理とは,「なんらかのクラス」において記述された論理式を「なんらかの効率の良さで」でモデル検査可能であることを示す定理である.グラフと一階述語論理式が与えられたとき,その論理式がグラフ上で成立するかどうかを判定する問題の固定パラメータ容易性について紹介する.(著者抄録)

シソーラス用語： *グラフ ,  論理学 ,  *命題論理 ,  述語論理 ,  *定理
準シソーラス用語： *アルゴリズム的メタ定理 ,  メタ定理 ,  *一階述語論理 ,  数理論理学 ,  *疎グラフ

分類 (2件)： 数値解析,近似法  (AB04000F) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： グラフ ,  アルゴリズム ,  定理