On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
From MaRDI portal
Publication:1680511
DOI10.1016/j.ic.2017.11.002zbMath1380.68228OpenAlexW2767555606MaRDI QIDQ1680511
Dimitrios M. Thilikos, Ge Xia, Iyad A. Kanj
Publication date: 16 November 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2017.11.002
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Succinct certification of monotone circuits ⋮ Succinct monotone circuit certification: planarity and parameterized complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Upper bounds for monotone planar circuit value and variants
- On the induced matching problem
- Polynomial time approximation schemes and parameterized complexity
- Treewidth. Computations and approximations
- On the complexity of planar Boolean circuits
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Completely inapproximable monotone and antimonotone parameterized problems
- Contraction obstructions for treewidth
- The complexity of polynomial-time approximation
- Genus characterizes the complexity of certain graph problems: Some tight results
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Applications of a Planar Separator Theorem
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- (Meta) Kernelization
- Theory and Applications of Satisfiability Testing
- Bidimensionality and Geometric Graphs
