From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes

DOI10.29007/C9F6MaRDI QIDQ4645742zbMATH OpenOpenAlexFDO

Authors Yazid M. Boumarafi, Lakhdar Sais, Yakoub Salhi

Publication date 10 January 2019

Published in EPiC Series in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.29007/c9f6

zbMATH Keywords

maximum independent setpropositional satisfiabilitytractable classes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On reducing maximum independent set to minimum satisfiability
• A new tractable class of constraint satisfaction problems
• A taxonomy of exact methods for partial Max-SAT
• An upper bound for resolution size: characterization of tractable SAT instances
• A note on the use of independent sets for the k-SAT problem
• scientific article; zbMATH DE number 1559517
• New upper bounds for the problem of maximal satisfiability
• New tableau characterizations for non-clausal \textsc{MaxSAT} problem

This page was built for publication: From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes

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