Testing satisfiability

DOI10.1016/S0196-6774(03)00019-1MaRDI QIDQ4420420zbMATH OpenFDO

Authors Noga Alon, Asaf Shapira

Publication date 17 August 2003

Published in Journal of Algorithms (Search for Journal in Brave)

zbMATH Keywords

Property testingSatisfiabilityHypergraph coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 956865
• Algorithms for testing satisfiability formulas
• Algorithms for testing the satisfiability of propositional formulae
• A constructive investigation of satisfiability
• A simple test improves checking satisfiability
• Satisfiability checking: theory and applications
• Satisfiability checking and symbolic computation

Cited in

(12)

• Testing subgraphs in directed graphs
• A proof of Green's conjecture regarding the removal properties of sets of linear equations
• (Quantum) complexity of testing signed graph clusterability
• Testing permutation properties through subpermutations
• Testing list H-homomorphisms
• Finding cycles and trees in sublinear time
• High Quality Test Pattern Generation and Boolean Satisfiability
• Testing hypergraph colorability
• Distribution-free connectivity testing for sparse graphs
• A characterization of testable hypergraph properties
• scientific article; zbMATH DE number 2119722 (Why is no real title available?)
• Testing quantum satisfiability

This page was built for publication: Testing satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4420420)