Article ID Journal Published Year Pages File Type
6873927 Information and Computation 2017 18 Pages PDF
Abstract
We study the parameterized complexity of and with respect to the genus of the underlying circuit. We give tight results, and draw a map of the parameterized complexity of these problems with respect to the genus of the circuit. As a byproduct of our results, we obtain tight characterizations of the parameterized complexity of several problems with respect to the genus of the underlying graph.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
Authors
, , ,