文献

J-GLOBAL ID：202202281432920298   整理番号：22A0322394

Hフリーエッジ修正問題の非圧縮性:二分法に向けて【JST・京大機械翻訳】

Incompressibility of H-free edge modification problems: Towards a dichotomy

著者 (2件)： Marx Daniel (CISPA Helmholtz Center for Information Security, Germany) ,  Sandeep R.B. (Department of Computer Science and Engineering, Indian Institute of Technology Dharwad, India)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 125  ページ： 25-58  発行年： 2022年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGと整数kを与えられた場合,H-フリーEdge Editing問題は,G中のペアの隣接を,Hの誘起コピーなしにグラフに変化させるように,G中の頂点のほとんどのk対に存在するかどうかを見つけることである。非自明多項式カーネルは,ほとんどの4頂点を持ついくつかのグラフHに対して存在することが知られているが,5頂点から始まり,多項式カーネルは,Hが完全または空である場合にのみ知られている。これは,HフリーEdge Editingが多項式カーネルを許す少なくとも5頂点を持つ他のHがないという推測を示唆する。この目標に向けて,著者らは,あらゆるH∈H,HフリーEdge Editingが非圧縮性であり,複雑性仮定NPが,非圧縮であり,そして,複雑性仮定NPが,共NP/polyを保持し,次に,HフリーEdge Editingが,完全も空もない少なくとも5つの頂点を有するあらゆるグラフHに対して非圧縮性である,というような9つの5頂点グラフのセットHを得るものである。”H-free Edge Editing”は,非圧縮的で,そして,H-フリーEdge Editingは,すべてのグラフHに対して非圧縮である。また,HフリーEdge欠失/Completionに対しても同様の結果を得た。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *グラフ ,  多項式 ,  誘導 ,  端部 ,  頂点 ,  非圧縮性
準シソーラス用語： 複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： 非圧縮性 ,  エッジ修正問題 ,  Hフリーグラフ

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： エッジ ,  問題 ,  非圧縮性