2013/03/11 by Nikolay Lavnikevich, Lavnikevich, Nikolay
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1303.2546
17 pages
arxiv created 2013/03/11 · arxiv updated 2013/03/12
Maximum Clique Problem(MCP) is one of the 21 original NP--complete problems enumerated by Karp in 1972. In recent years a large number of exact methods to solve MCP have been appeared(Babel, Wood, Kumlander, Fahle, Li, Tomita and etc). Most of them are branch and bound algorithms that use branching rule introduced by Balas and Yu and based on coloring heuristics to establish an upper bound on the clique number. They differ from each other primarily in vertex preordering and vertex coloring methods. Current methods of worst case running time analysis for branch and bound algorithms do not allow to provide tight upper bounds. This motivates the study of lower bounds for such algorithms. We prove 2^(n\5) lower bound for group of MCP algorithms based on usage of coloring heuristics.