文献

J-GLOBAL ID：202002234841163799   整理番号：20A1495525

発生ツリー幅によりパラメータ化した命題モデル計数のための高速アルゴリズム【JST・京大機械翻訳】

A Faster Algorithm for Propositional Model Counting Parameterized by Incidence Treewidth

著者 (2件)： Slivovsky Friedrich (TU Wien, Vienna, Austria) ,  Szeider Stefan (TU Wien, Vienna, Austria)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12178  ページ： 267-276  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 命題モデル計数問題(#SAT)は,入射グラフの与えられたツリー分解の幅kによってパラメータ化するとき,固定パラメータ-牽引可能(FPT)として知られている。最も速い既知のFPTアルゴリズムの実行時間は,[数式:原文を参照]の指数因子を含んだ。著者らは,部分モデル数を表す関数のζ変換とカバー製品を計算するための高速アルゴリズムを用いて[数式:原文を参照]にこの因子を改善し,それにより,プライムグラフのより少ない一般的ツリー幅によってパラメータ化されたFPTアルゴリズムと同じ実行時間を達成した。著者らの新しいアルゴリズムは,強力な指数時間仮説(SETH)が失敗する限り,漸近的に最適である。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  *高速アルゴリズム ,  *命題 ,  パラメタリゼーション
準シソーラス用語： 実行時間 , 【Automatic Indexing@JST】

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (5件)： パラメータ ,  命題 ,  モデル ,  計数 ,  高速アルゴリズム