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

DOI10.29007/c9f6zbMath1403.68073OpenAlexW4300551516MaRDI QIDQ4645742

Yazid M. Boumarafi, Yakoub Salhi, Lakhdar Saïs

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

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

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