Infra-chromatic bound for exact maximum clique search |
| |
| Affiliation: | 1. Department of Engineering Science, Faculty of Informatics and Engineering, The University of Electro-Communications, Chofu, Tokyo 182-8585, Japan;2. Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology, Kitakyushu 808-0196, Japan;3. CREST, Japan Science and Technology Agency (JST), Kawaguchi, Saitama 332-0012, Japan;1. Ecomaterials and Renewable Energy Research Center (ERERC), Department of Physics, Nanjing University, Nanjing 210093, Jiangsu, China;2. Jiangsu Key Laboratory for Nano Technology, Nanjing National Laboratory of Solid State Microstructures, College of Engineering and Applied Sciences, Nanjing University, Nanjing 210093, Jiangsu, China;3. Key Laboratory of Flexible Electronics (KLOFE) & Institute of Advanced Materials (IAM), Jiangsu National Synergetic Innovation Center for Advanced Materials (SICAM), Nanjing Tech University, Nanjing 211816, Jiangsu, China;4. Department of Engineering Science, The University of Electro Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan;5. Electronic Information Engineering College of Sanjiang University, Nanjing 210012, Jiangsu, China |
| |
| Abstract: | Many efficient exact branch and bound maximum clique solvers use approximate coloring to compute an upper bound on the clique number for every subproblem. This technique reasonably promises tight bounds on average, but never tighter than the chromatic number of the graph.Li and Quan, 2010, AAAI Conference, p. 128–133 describe a way to compute even tighter bounds by reducing each colored subproblem to maximum satisfiability problem (MaxSAT). Moreover they show empirically that the new bounds obtained may be lower than the chromatic number.Based on this idea this paper shows an efficient way to compute related “infra-chromatic” upper bounds without an explicit MaxSAT encoding. The reported results show some of the best times for a stand-alone computer over a number of instances from standard benchmarks. |
| |
| Keywords: | Approximate coloring Branch-and-bound MaxSAT Combinatorial optimization |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
