Solving maximum weight clique using maximum satisfiability reasoning

zbMATH Open1366.90176MaRDI QIDQ5282985FDOQ5282985

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

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

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)

Cited In (6)

• Old techniques in new ways: clause weighting, unit propagation and hybridization for maximum satisfiability
• A Max-SAT Inference-Based Pre-processing for Max-Clique
• On graphs with polynomially solvable maximum-weight clique problem
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• Clique inference process for solving Max-CSP

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)