On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
type: Item
instance of: scholarly article
title: On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
zbMATH Open document ID: 1380.68228
author: Dimitrios M. Thilikos
author: Ge Xia
author: Iyad Kanj
published in: Information and Computation
publication date: 2017-11-16T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6807531
zbMATH Keywords: weighted satisfiability
zbMATH Keywords: parameterized complexity
zbMATH Keywords: genus
MaRDI profile type: Publication
full work available at URL: j.ic.2017.11.002
OpenAlex ID: W2767555606
cites work: Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
cites work: (Meta) Kernelization
cites work: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
cites work: The complexity of polynomial-time approximation
cites work: Polynomial time approximation schemes and parameterized complexity
cites work: Genus characterizes the complexity of certain graph problems: Some tight results
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Bidimensionality: new connections between FPT algorithms and PTASs
cites work: Q4393480
cites work: Contraction obstructions for treewidth
cites work: Q5365078
cites work: Bidimensionality and Geometric Graphs
cites work: Q3757929
cites work: On the induced matching problem
cites work: Treewidth. Computations and approximations
cites work: Upper bounds for monotone planar circuit value and variants
cites work: Applications of a Planar Separator Theorem
cites work: Completely inapproximable monotone and antimonotone parameterized problems
cites work: Theory and Applications of Satisfiability Testing
cites work: On the complexity of planar Boolean circuits
cites work: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
cites work: Q3762226
cites work: Q4869540
DOI: 10.1016/J.IC.2017.11.002
description: scientific article; zbMATH DE number 6807531