On Reducing Maximum Independent Set to Minimum Satisfiability

DOI10.1007/978-3-319-09284-3_9zbMath1423.68452OpenAlexW2162181360MaRDI QIDQ3192058

Alexey Ignatiev, Antonio Morgado, João P. Marques-Silva

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-09284-3_9

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)

Related Items (4)

A primal-dual approximation algorithm for \textsc{minsat} ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ A non-clausal tableau calculus for \textsc{MinSat} ⋮ Iterated local search with Trellis-neighborhood for the partial Latin square extension problem

Uses Software

• Algorithm 787

This page was built for publication: On Reducing Maximum Independent Set to Minimum Satisfiability