文献

J-GLOBAL ID：202002259286329903   整理番号：20A1929011

一般的および分数的ハイパーツリー分解はハードおよび容易の場合【JST・京大機械翻訳】

General and Fractional Hypertree Decompositions Hard and Easy Cases

著者 (3件)： Fischl Wolfgang (TU Wien, Vienna, Austria) ,  Gottlob Georg (University of Oxford & TU Wien, Oxford, Austria) ,  Pichler Reinhard (TU Wien, Vienna, Austria)
資料名： ACM Proceedings  (ACM Proceedings)
号： SIGMOD/PODS ’18  ページ： 17-32  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ハイパーツリー分解,ならびにより強力な一般化ハイパーツリー分解(GHDs),およびより一般的な分数ハイパーツリー分解(FHD)は,コンジュニティブクエリーと制約充足問題の解答のためにうまく用いられる超グラフ分解法である。あらゆるハイパーグラフHは,これらの方法のそれぞれに対して幅を持つ:そのハイパーツリー幅hw(H),その一般化ハイパーツリー幅ghw(H),およびその分数ハイパーツリー幅fhw(H)。hw(H)≦kは固定kの多項式時間でチェックできるが,ghw(H)≦kはk>=3でNP完全であることが知られている。固定kに対するfhw(H)≦k検査の複雑性は10年以上にわたって開かれた。著者らは,fhw(H)≦kのチェックがk=2であってもNP完全であることを示すことにより,この未解決問題を解いた。同じ構成により,k=2に対するghw(H)≦kの検査のNP完全性も証明できた。これらの結果を証明した後,有界ghwまたはfhwの検査が扱いやすいという意味ある制約を同定した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 分割法 ,  *超グラフ ,  制約充足問題
準シソーラス用語： 複雑性 ,  多項式時間 ,  有界 ,  未解決問題 , 【Automatic Indexing@JST】

著者キーワード (4件)： 超グラフ分解法 ,  np完全性 ,  扱いやすいフラグメント ,  扱いやすい質問応答

分類 (3件)： 進化論一般  (EC03010Q) ,  生物科学一般  (EA01010W) ,  分子・遺伝情報処理  (JE15040B)

タイトルに関連する用語 (3件)： 分数 ,  分解 ,  容易