Hits:

Indexed by:会议论文

Date of Publication:2017-04-16

Included Journals:EI、CPCI-S、Scopus

Page Number:311-316

Key Words:parameterized complexity; monotone circuit value problem; parallel algorithm

Abstract: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.