Succinct monotone circuit certification: planarity and parameterized complexity

DOI10.1007/978-3-030-58150-3_40MaRDI QIDQ2019496zbMATH OpenOpenAlexFDO

Authors Mateus Rodrigues Alves, Mateus de Oliveira Oliveira, Janio Carlos Nascimento Silva, Uéverton dos Santos Souza

Publication date 21 April 2021

Full work available at URL https://doi.org/10.1007/978-3-030-58150-3_40

zbMATH Keywords

FPTgenusmonotone circuitsplanaritytreewidth

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• Completely inapproximable monotone and antimonotone parameterized problems
• Contraction obstructions for treewidth
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 1256750 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• On the complexity of planar Boolean circuits
• On the Computational Power of Threshold Circuits with Sparse Activity
• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
• Quickly excluding a planar graph
• Revisiting the complexity of and/or graph solution
• The complexity of polynomial-time approximation
• Theory and Applications of Satisfiability Testing
• Tractability, hardness, and kernelization lower bound for and/or graph solution
• Upper bounds for monotone planar circuit value and variants

Cited in

(4)

• Succinct certification of monotone circuits
• Computing the best-case energy complexity of satisfying assignments in monotone circuits
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Evaluating Monotone Circuits on Cylinders, Planes and Tori

This page was built for publication: Succinct monotone circuit certification: planarity and parameterized complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019496)