Succinct monotone circuit certification: planarity and parameterized complexity
type: Item
instance of: scholarly article
title: Succinct monotone circuit certification: planarity and parameterized complexity
DOI: 10.1007/978-3-030-58150-3_40
author: Mateus Rodrigues Alves
author: Mateus de Oliveira Oliveira
author: Janio Carlos Nascimento Silva
author: Uéverton dos Santos Souza
publication date: 2021-04-21T00:00:00Z
Mathematics Subject Classification ID: 68Rxx
zbMATH DE Number: 7336129
zbMATH Keywords: monotone circuits
zbMATH Keywords: planarity
zbMATH Keywords: genus
zbMATH Keywords: FPT
zbMATH Keywords: treewidth
MaRDI profile type: Publication
full work available at URL: 978-3-030-58150-3 40
OpenAlex ID: W3081929894
cites work: The complexity of polynomial-time approximation
cites work: Parameterized complexity of weighted satisfiability problems: decision, enumeration, counting
cites work: Q4393480
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Contraction obstructions for treewidth
cites work: Improved bounds on the planar branchwidth with respect to the largest grid minor size
cites work: On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
cites work: Q4228486
cites work: Upper bounds for monotone planar circuit value and variants
cites work: Completely inapproximable monotone and antimonotone parameterized problems
cites work: Quickly excluding a planar graph
cites work: Graph minors. III. Planar tree-width
cites work: Tractability, hardness, and kernelization lower bound for and/or graph solution
cites work: Revisiting the complexity of and/or graph solution
cites work: Theory and Applications of Satisfiability Testing
cites work: On the complexity of planar Boolean circuits
cites work: On the Computational Power of Threshold Circuits with Sparse Activity
description: scientific article; zbMATH DE number 7336129