Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
type: Item
instance of: scholarly article
title: Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
zbMATH Open document ID: 1485.90119
published in: Annals of Mathematics and Artificial Intelligence
publication date: 2022-02-14T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C09
zbMATH DE Number: 7473192
zbMATH Keywords: 2CNF
zbMATH Keywords: read-once resolution
zbMATH Keywords: NP-hard
zbMATH Keywords: exact exponential algorithms
Wikidata QID: Q113904581
author: K. Subramani
author: Piotr Wojciechowski
MaRDI profile type: Publication
full work available at URL: s10472-021-09762-2
OpenAlex ID: W3175751884
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: On the complexity of approximating the independent set problem
cites work: The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification
cites work: Minimum Witnesses for Unsatisfiable 2CNFs
cites work: Q4255462
cites work: Q2934608
cites work: Q3651735
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: On finding short resolution refutations and small unsatisfiable subsets
cites work: Exact exponential algorithms.
cites work: Kernelization
cites work: The intractability of resolution
cites work: Q4699307
cites work: Q4764626
cites work: Finding read-once resolution refutations in systems of 2CNF clauses
cites work: Restricted cutting plane proofs in Horn constraint systems
cites work: Read-once resolutions in Horn formulas
cites work: Q4471290
cites work: Renaming a Set of Clauses as a Horn Set
cites work: What is answer set programming to propositional satisfiability
cites work: Answer Set Programming
cites work: Q4231923
cites work: Q4298260
cites work: Q4539605
DOI: 10.1007/S10472-021-09762-2
Recommended article: Finding read-once resolution refutations in systems of 2CNF clauses
Recommended article: On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas
Recommended article: Minimum 2CNF Resolution Refutations in Polynomial Time
Recommended article: Exact and parameterized algorithms for read-once refutations in Horn constraint systems
Recommended article: The Complexity of Finding Read-Once NAE-Resolution Refutations
Recommended article: On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems
Recommended article: Optimal length tree-like resolution refutations for 2SAT formulas
Recommended article: Q4417352
Recommended article: Read-once refutations in Horn constraint systems: an algorithmic approach
Recommended article: A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
description: scientific article; zbMATH DE number 7473192