Generalizations of matched CNF formulas

DOI10.1007/s10472-005-0432-6zbMath1099.68044OpenAlexW4237683073MaRDI QIDQ1777405

Stefan Szeider

Publication date: 13 May 2005

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-005-0432-6

zbMATH Keywords

bipartite graphNP-completenessSAT problempolynomial hierarchydeficiencybiclique covermatched formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

Coherent network partitions: characterizations with cographs and prime graphs ⋮ Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable ⋮ Coherent network partitions ⋮ Complexity of secure sets ⋮ Complexity of Secure Sets ⋮ Backdoor sets of quantified Boolean formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simplified NP-complete satisfiability problem
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Matching theory
• The polynomial-time hierarchy
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Investigations on autark assignments
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• A perspective on certain polynomial-time solvable classes of satisfiability
• Minimal Unsatisfiable Formulas with Bounded Clause-Variable Difference are Fixed-Parameter Tractable
• Complexity results for some eigenvector problems

This page was built for publication: Generalizations of matched CNF formulas