@inproceedings{KANAHARA-ICCCM-2022,
title = {The performance of a local search based on vertex coloring for the maximum clique problem},
author = {Kazuho Kanahara and Shun Ito and Kengo Katayama},
doi = {https://doi.org/10.1145/3556223.3556235},
year = {2022},
date = {2022-10-16},
urldate = {2022-10-16},
booktitle = {ICCCM 2022: Proceedings of the 10th International Conference on Computer and Communications Management},
pages = {79-83},
abstract = {The maximum clique problem (MCP) is a fundamental combinatorial optimization problem that has many practical applications. In the exact methods, the idea of approximate coloring of vertices has been employed in the one proposed by Tomita, et al. in 1970's in order to prune unnecessary searching, and it now has become the important idea in the field of developing efficient exact algorithms for solving MCP. On the other hand, in the heuristic and metaheuristic research fields, few heuristics have been presented for MCP that use vertex coloring, and the search performance of a local search using the degree of saturation based on vertex coloring information is not clear. In this paper, we investigate the performance of a Local Search based on vertex coloring for MCP. Experimental results on the benchmark graphs show that the proposed algorithm is more effective than other simple Local Search for several difficult graphs such as perfect graphs.},
keywords = {Local search, Maximum clique problem, Vertex coloring},
pubstate = {published},
tppubtype = {inproceedings}
}
