文献

J-GLOBAL ID：201702260077774385   整理番号：17A0966779

有界種数を持つ単調回路値問題のための新しい並列アルゴリズム【Powered by NICT】

A new parallel algorithm for monotone circuit value problem with bounded genus

著者 (5件)： Lai Xiaochen (School of Software, Dalian University of Technology, Key Laboratory for Ubiquitous Network and Service Software, Dalian, China, 116024) ,  Shi Wenzhe (School of Software, Dalian University of Technology, Dalian, China, 116024) ,  Liu Xin (School of Software, Dalian University of Technology, Dalian, China, 116024) ,  Fu Manqing (School of Software, Dalian University of Technology, Dalian, China, 116024) ,  Li Shouwei (Heinz Nixdorf Institute and Department of Computer Science, Paderborn University, Paderborn, Germany, 33102)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICIST  ページ： 311-316  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 固定パラメータ並列実行可能と呼ばれる効率的に並列化可能なパラメータ化された問題を特性化するための新しい複雑さクラスを提案した(FPPT)。FPPT=FPP,それらは互いに変換できるが,FPPTであるFPPよりもはるかに簡単で妥当であった。FPPTの視点は重要な固有問題に集中することを可能にする,NCからP完全問題を移動させるために各パラメータの寄与を理解することである。も基礎となるグラフの属によってパラメータ化された単調回路値問題のための新しい並列アルゴリズム,深さ優先探索とPCツリーデータ構造に基づくのみを開発した。著者らのアルゴリズムは,この問題はFPPTのであることを意味する。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： グラフ ,  パラメタリゼーション ,  キャラクタリゼーション ,  *アルゴリズム ,  *並列アルゴリズム
準シソーラス用語： ツリーデータ構造 ,  深さ優先探索 ,  複雑性 ,  *種数 ,  *有界 , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (4件)： 有界 ,  種数 ,  問題 ,  並列アルゴリズム