---
res:
bibo_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 O(m) instead of O(n2) parallel processors, the running time improves
from 4logn+O(kk) to O(k⋅log3n), 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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Faisal N.
foaf_name: Abu-Khzam, Faisal N.
foaf_surname: Abu-Khzam
- foaf_Person:
foaf_givenName: Shouwei
foaf_name: Li, Shouwei
foaf_surname: Li
- foaf_Person:
foaf_givenName: Christine
foaf_name: Markarian, Christine
foaf_surname: Markarian
foaf_workInfoHomepage: http://www.librecat.org/personId=37612
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
- foaf_Person:
foaf_givenName: Pavel
foaf_name: Podlipyan, Pavel
foaf_surname: Podlipyan
bibo_doi: 10.1007/978-3-319-48749-6_35
dct_date: 2016^xs_gYear
dct_language: eng
dct_title: On the Parameterized Parallel Complexity and the Vertex Cover Problem@
...