Succinct monotone circuit certification: planarity and parameterized complexity

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

zbMATH Keywords

monotone circuitstreewidthplanaritygenusFPT

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

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