On reducing maximum independent set to minimum satisfiability

DOI10.1007/978-3-319-09284-3_9MaRDI QIDQ3192058zbMATH OpenOpenAlexFDO

Authors A. A. Ignatiev, Antonio Morgado, Joao 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

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 approximation algorithms for the minimum satisfiability problem
• On the power of simple reductions for the maximum independent set problem
• A method of graph reduction and its applications
• Reductions for the stable set problem
• scientific article; zbMATH DE number 1305487

Cited in

(8)

• Minimal sets on propositional formulae. Problems and reductions
• A primal-dual approximation algorithm for \textsc{minsat}
• A non-clausal tableau calculus for \textsc{MinSat}
• New properties of maximum independent set problem solution truncation rules or redundant branches
• On the power of simple reductions for the maximum independent set problem
• From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes
• Iterated local search with Trellis-neighborhood for the partial Latin square extension problem
• Partial minimum satisfiability: fine-grained analysis

Describes a project that uses

Uses Software

• Algorithm 787

This page was built for publication: On reducing maximum independent set to minimum satisfiability

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