A Max-SAT Inference-Based Pre-processing for Max-Clique

DOI10.1007/978-3-540-79719-7_13MaRDI QIDQ3502702zbMATH OpenOpenAlexFDO

Authors Federico Heras, Javier Larrosa

Publication date 27 May 2008

Published in Theory and Applications of Satisfiability Testing – SAT 2008 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79719-7_13

zbMATH Keywords

Max-SATInferenceMax-clique

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• SAT-based preprocessing for MaxSAT
• A Preprocessor for Max-SAT Solvers
• Solving maximum weight clique using maximum satisfiability reasoning
• New inference rules for Max-SAT
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem

Cites work

• scientific article; zbMATH DE number 5547826 (Why is no real title available?)
• scientific article; zbMATH DE number 1947416 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• scientific article; zbMATH DE number 5226464 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• A fast algorithm for the maximum clique problem
• A logical approach to efficient Max-SAT solving
• A new trust region technique for the maximum weight clique problem
• An algorithm for finding a maximum clique in a graph
• An exact algorithm for the maximum clique problem
• Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT Solvers
• Finding a Maximum Clique in an Arbitrary Graph
• Intelligent variable orderings and re-orderings in DAC-based solvers for WCSP
• New Upper Bounds for Maximum Satisfiability
• Optimal Protein Structure Alignment Using Maximum Cliques
• Resolution for Max-SAT
• Solving Max-SAT as weighted CSP
• Solving weighted CSP by maintaining arc consistency
• The first and second Max-SAT evaluations
• Theory and Applications of Satisfiability Testing
• Using constraint programming to solve the maximum clique problem

Cited in

(5)

• Clique Inference Process for Solving Max-CSP
• Solving maximum weight clique using maximum satisfiability reasoning
• Clique inference process for solving Max-CSP
• Incomplete inference for graph problems
• Russian doll search for the Steiner triple covering problem

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: A Max-SAT Inference-Based Pre-processing for Max-Clique

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