Paper Info
Title
Parameterized Parallel Complexity
Abstract
Abstract: We consider the framework of Parameterized Complexity and we investigate the issue of whichproblems do admit efficient fixed parameter parallel algorithms. In particular, we introduce two classesof efficiently parallelizable parameterized problems, PNC and FPP, according to the degree of efficiencywe want to obtain. We sketch both some FPP-algorithms solving natural parameterized problems and auseful tool for proving membership to FPP based on the concept of treewidth. We then focus our...
Year
DOI
Venue
1998
10.1007/BFb0057945
Electronic Colloquium on Computational Complexity (ECCC)
Keywords
DocType
Volume
parameterized parallel complexity,parameterized complexity,parallel algorithm
Conference
4
Issue
ISSN
ISBN
6
0302-9743
3-540-64952-2
Citations 
PageRank 
References 
5
0.62
15
Authors
2
Name
Order
Citations
PageRank
Marco Cesati118512.53
Miriam di Ianni214417.27