Solving maximum weight clique using maximum satisfiability reasoning

MaRDI QIDQ5282985zbMATHFDO

Authors Zhiwen Fang, Chu-Min Li, Kan Qiao, Xu Feng, Ke Xu

Publication date 18 July 2017

Full work available at URL http://ebooks.iospress.nl/volumearticle/36957

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• A Max-SAT Inference-Based Pre-processing for Max-Clique
• Solving Max-SAT as weighted CSP
• A logical approach to efficient Max-SAT solving
• Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability

Cited in

(9)

• Clique inference process for solving Max-CSP
• Maximum clique via \textsc{MaxSat} and back again
• Incomplete inference for graph problems
• An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability
• On graphs with polynomially solvable maximum-weight clique problem
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• A Max-SAT Inference-Based Pre-processing for Max-Clique

Describes a project that uses

Uses Software

• BHOSLIB

This page was built for publication: Solving maximum weight clique using maximum satisfiability reasoning

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