Succinct monotone circuit certification: planarity and parameterized complexity
From MaRDI portal
Publication:2019496
DOI10.1007/978-3-030-58150-3_40OpenAlexW3081929894MaRDI QIDQ2019496
Uéverton dos Santos Souza, Mateus Rodrigues Alves, Mateus de Oliveira Oliveira, Janio Carlos Nascimento Silva
Publication date: 21 April 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_40
Related Items (2)
Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Succinct certification of monotone circuits
Cites Work
- Unnamed Item
- Unnamed Item
- Revisiting the complexity of and/or graph solution
- Upper bounds for monotone planar circuit value and variants
- Graph minors. III. Planar tree-width
- On the parameterized complexity of multiple-interval graph problems
- Quickly excluding a planar graph
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- On the complexity of planar Boolean circuits
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Completely inapproximable monotone and antimonotone parameterized problems
- Contraction obstructions for treewidth
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- The complexity of polynomial-time approximation
- Parameterized Complexity of Weighted Satisfiability Problems: Decision, Enumeration, Counting
- On the Computational Power of Threshold Circuits with Sparse Activity
- Theory and Applications of Satisfiability Testing
This page was built for publication: Succinct monotone circuit certification: planarity and parameterized complexity
