点击次数：

论文类型：会议论文

发表时间：2017-04-16

收录刊物：EI、CPCI-S、Scopus

页面范围：311-316

关键字：parameterized complexity; monotone circuit value problem; parallel algorithm

摘要：We propose a new complexity class to characterize the efficiently parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). Although FPPT = FPP and they can be transformed one another, FPPT is much simpler and reasonable than FPP. The viewpoint of FPPT allows us to concentrate on important intrinsic issues, such as to understand the contribution of each parameter to transfer a problem from NC to P-complete. We also develop a new parallel algorithm for the monotone circuit value problem parameterized by the genus of the underlying graphs, which only based on depth-first search and the PC-tree data structure. Our algorithm implies this problem is in FPPT.