文献

J-GLOBAL ID：201902238502470865   整理番号：19A2034582

相補的最大ストリップ回復のための改良線形カーネル:単純化と小型化【JST・京大機械翻訳】

An improved linear kernel for complementary maximal strip recovery: Simpler and smaller

著者 (6件)： Li Wenjun (School of Computer and Communication Engineering, Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, Changsha University of Science and Technology, Changsha, China) ,  Liu Haiyan (School of Computer and Communication Engineering, Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, Changsha University of Science and Technology, Changsha, China) ,  Wang Jianxin (School of Information Science and Engineering, Central South University, Changsha, China) ,  Xiang Lingyun (School of Computer and Communication Engineering, Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, Changsha University of Science and Technology, Changsha, China) ,  Yang Yongjie (School of Information Science and Engineering, Central South University, Changsha, China) ,  Yang Yongjie (Chair of Economic Theory, Universitaet des Saarlandes, Saarbruecken, Germany)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 786  ページ： 55-66  発行年： 2019年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ここでは,与えられた2つの文字列S1とS2の異なる文字列の2つのストリングS1とS2が正の形または負の形のいずれかで現れる,完全な最大ストリップ回復問題(CMSR)を研究した。問題は,2つの整合したストリングを削除するk文字があるかどうかである。S1とS2の分割が少なくとも2つの文字を含み,S1の分割の各成分S2jに対して,文字の順序を最初に逆転させ,次に文字を否定することにより,S1の分割のS2を,S1とS2の分割において,S1の分割において,S2の分割において特異的な成分S2jが存在する。CMSR問題は,kに関してNP困難で固定パラメータ追跡可能であることが知られている。特に,サイズ74K+4の線形カーネルを8つの縮小規則に基づいて開発した。最近,3つの新しい縮小ルールを以前のカーネル化に課すことにより,線形カーネルは58Kに改善された。著者らは,カーネル化を単純化することを目的としているが,しかし,改良カーネルを得た。特に,サイズ42k+24の線形カーネルを導く7つの還元則を研究した。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *小型化 ,  *簡素化 ,  NP困難 ,  *帯板 ,  *線形性 ,  文字列

著者キーワード (4件)： 相補的最大ストリップ回復 ,  線形カーネル ,  カーネル化 ,  固定パラメータ追跡表

分類 (4件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A) ,  人工知能  (JE08000Z) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (5件)： ストリップ ,  回復 ,  線形 ,  カーネル ,  単純化