Name
Abstract | ||
|---|---|---|
Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using (mathcal {O}(m)) instead of (mathcal {O}(n^2)) parallel processors, the running time improves from (4log n + mathcal {O}(k^k)) to (mathcal {O}(kcdot log ^3 n)), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus. |
Year | Venue | Field |
|---|---|---|
2016 | COCOA | Kernelization,Parallelizable manifold,Discrete mathematics,Parameterized complexity,Combinatorics,Vertex (geometry),Edge cover,Vertex (graph theory),Computer science,Vertex cover,Feedback vertex set |
DocType | Citations | PageRank |
Conference | 1 | 0.35 |
References | Authors | |
11 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Faisal N. Abu Khzam | 1 | 404 | 36.25 |
| Shouwei Li | 2 | 1 | 2.04 |
| Christine Markarian | 3 | 1 | 1.71 |
| Friedhelm Meyer auf der Heide | 4 | 1744 | 238.01 |
| Pavel Podlipyan | 5 | 1 | 2.04 |