---
res:
bibo_abstract:
- 'We present an efficient parallel algorithm for the general Monotone Circuit Value
Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm
generalizes a recent result by Limaye et al. who showed that MCVP with toroidal
embedding (genus 1) is in NC when the input contains a toroidal embedding of the
circuit. In addition to extending this result from genus 1 to any bounded genus
k, and unlike the work reported by Limaye et al., we do not require a precomputed
embedding to be given. Most importantly, our results imply that given a P-complete
problem, it is possible to find an algorithm that makes the problem fall into
NC by fixing one or more parameters. Hence, we deduce the interesting analogy:
Fixed Parameter Parallelizable (FPP) is with respect to P-complete what Fixed
Parameter Tractable (FPT) is with respect to NP-complete. Similar work that uses
treewidth as parameter was also presented by Elberfeld et al. in [6].@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-42634-1_8
dct_date: 2016^xs_gYear
dct_language: eng
dct_title: The Monotone Circuit Value Problem with Bounded Genus Is in NC@
...