文献

J-GLOBAL ID：202202216522662691   整理番号：22A0000769

誘引可能性の閾値について【JST・京大機械翻訳】

On the threshold of intractability

著者 (4件)： Drange Pal Gronas (University of Bergen, Norway) ,  Dregi Markus Fanebust (University of Bergen, Norway) ,  Lokshtanov Daniel (University of California, Santa Barbara, United States of America) ,  Sullivan Blair D. (University of Utah, United States of America)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 124  ページ： 1-25  発行年： 2022年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフ修正問題閾値Editingと連鎖編集の計算複雑性は,15年以上の計算グラフ理論における重要な未解決問題であった。これらの問題は,グラフを閾値または鎖グラフに変換するために,最も少ないエッジを付加し,削除することから成る。両問題はNP困難であることを示し,2001年からNatanzon,Shamir,Sharanによる予測を解決した。正側では,両問題は二次頂点カーネルをアドミットし,2O(√klogk)+nO(1)時間で両方の問題を解決するサブ指数時間パラメータ化アルゴリズムを与える。この複雑性クラスでは,自然問題は殆ど知られていない。また,これらの結果は,両方の問題の完了と欠失バリアントに拡張して,閾値/チェーングラフは,すべての3つのバージョン-完了,削除,および編集が,サブ指数パラメータ化時間においてNP完全と可解性の両方である唯一の既知のグラフクラスである。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： グラフ理論 ,  *計算量 ,  NP困難 ,  パラメタリゼーション
準シソーラス用語： 決定可能性 ,  複雑性 ,  未解決問題 ,  パラメータ化アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (3件)： エッジ編集 ,  閾値グラフ ,  パラメータ化複雑性

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

タイトルに関連する用語 (3件)： 誘引 ,  可能性 ,  閾値