2017/04/04 by Nikolay Lavnikevich, Nikolay, Lavnikevich
Computer Science · Engineering · #05C85 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Optimization and Search Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1704.00908
openalex publication_date 2017/04/04 · openalex created_date 2017/05/19 · openalex updated_date 2026/07/28
Given simple undirected graph G = (V, E), the Maximum Clique Problem(MCP) is that of finding a maximum-cardinality subset Q of V such that any two vertices in Q are adjacent. We present a modified local search algorithm for this problem. Our algorithm build some maximal solution and can determine in polynomial time if a maximal solution can be improved by replacing a single vertex with k, k > 1, others. We test our algorithms on DIMACS[5], Sloane[15], BHOSLIB[1], Iovanella[8] and our random instances.