2010/11/24 by Rastislav Lenhardt, Lenhardt, Rastislav
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1011.5447
openalex publication_date 2010/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the last decade, the power of the state-of-the-art SAT and Integer\nProgramming solvers has dramatically increased. They implement many new\ntechniques and heuristics and since any NP problem can be converted to SAT or\nILP instance, we could take advantage of these techniques in general by\nconverting the instance of NP problem to SAT formula or Integer program. A\nproblem we consider, in this proof of concept, is finding a largest clique in a\ngraph. We ran several experiments on large random graphs and compared 3\napproaches: Optimised backtrack solution, Translation to SAT and Translation to\nInteger program. The last one was the fastest one.\n