A new exact algorithm for the maximum-weight clique problem based on a heuristic vertex-coloring and a backtrack search

Autor:	Mochamad Suyudi
Rok vydání:	2022
Předmět:	General Medicine
Zdroj:	International Journal of Global Operations Research. 3:132-136
ISSN:	2722-1016 2723-1747
DOI:	10.47194/ijgor.v3i4.79
Popis:	In this paper we present an exact algorithm for the maximum-weight clique problem on arbitrary undirected graphs. The algorithm based on a fact that vertices from the same independent set couldn’t be included into the same maximum clique. Those independent sets are obtained from a heuristic vertex coloring where each of them is a color class. Color classes and a backtrack search are used for pruning branches of the maximum-weight clique search tree. Those pruning strategies together result in a very effective algorithm for the maximum-weight clique finding. Computational experiments with random graphs show that the new algorithm works faster than earlier published algorithms; especially on dense graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::89af0662cd84786d44dff78af0a32763 https://doi.org/10.47194/ijgor.v3i4.79 Zobrazit plný text záznamu