文献

J-GLOBAL ID：202202233506062814   整理番号：22A0917409

非決定性FPT時間と対数空間のためのパラメータ化問題【JST・京大機械翻訳】

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

著者 (4件)： Bodlaender Hans L. (Utrecht University,Department of Information and Computing Sciences,Utrecht,The Netherlands) ,  Groenland Carla (Utrecht University,Department of Information and Computing Sciences,Utrecht,The Netherlands) ,  Nederlof Jesper (Utrecht University,Department of Information and Computing Sciences,Utrecht,The Netherlands) ,  Swennenhuis Celine M. F. (Eindhoven University of Technology,Department of Mathematics and Computer Science,Eindhoven,The Netherlands)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 193-204  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： XNLPはパラメータkを持つサイズnのインスタンスを時間f(k)nO(1)と空間f(k)log(n)(いくつかの計算可能関数f)で非決定論的に解くことができるように,パラメータ化プロブリーのクラスであると判断するものである。”XNLP”は,パラメータkを持つサイズnのインスタンスを,時間f(k)nO(1)と空間f(k)log(n)(いくつかの計算可能関数f)で非決定論的に解くことができる。著者らは,パラメータとして経路幅を有するList coloringand Precoloring Extension,例えば,パラメータとしての機械と部分順序幅,加重Cnf充足可能性と再構成問題の帯域幅と変種の両方を有する,List ColoringとPrecoloring拡張のような,多様なXNLP完全問題を与えた。特に,これら全ての問題は全てのtに対してW[t]困難であることを意味する。これはまた,帯域幅問題のパラメータ化複雑性に関する長い立位質問を回答する。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 再構成 ,  帯域幅 ,  *対数 ,  パラメタリゼーション ,  立位 ,  非決定性
準シソーラス用語： 複雑性 ,  満足化可能性 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (3件)： 非決定性 ,  対数 ,  パラメータ化