en fr The maximum clique problems with applications to graph coloring Problèmes de clique maximum avec applications à la coloration de graphe Reportar como inadecuado




en fr The maximum clique problems with applications to graph coloring Problèmes de clique maximum avec applications à la coloration de graphe - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 ICT - Institute of Computing Technology Beijing 2 LERIA - Laboratoire d-Etudes et de Recherche en Informatique d-Angers

Abstract : The maximum clique problem MCP is an important combinatorial optimization problem with a wide range of practical applications in numerous fields, including information retrieval, signal transmission analysis, classification theory, economics, scheduling, and biomedical engineering. Moreover, a number of combinatorial optimization problems are tightly related to MCP, such as graph coloring, sum coloring, set packing and optimal winner determination. This thesis is devoted to developing effective heuristic approaches to tackle the maximum clique problem and its generalizations. To achieve this, we developed an adaptive multistart tabu search approach for the classic maximum clique problem, a multi-neighborhood tabu search algorithm for the maximum vertex weight clique and a hybrid metaheuristic method for the maximum edge weight clique problem. Moreover, we apply these developed heuristic approaches to solve these hard problems which are tightly related to the maximum clique problem. All algorithms are implemented and successfully tested on a number of benchmark instances from diverse application areas. The proposed methods favorably compete with other state-of-art approaches.

Résumé : Le problème de la clique maximum MCP est un problème d-optimisation combinatoire important avec un large éventail d-applications pratiques dans de nombreux domaines, y compris la recherche d-information, l-analyse de la transmission du signal, la théorie de la classification, l-économie, la planification et l-ingénierie biomédicale. En outre, un certain nombre de problèmes d-optimisation combinatoire sont étroitement liés au MCP, tels que la coloration de graphe, la somme coloration, réglez détermination du gagnant emballage et optimale. Cette thèse est consacrée à l-élaboration d-approches heuristiques efficaces pour s-attaquer au problème de la clique maximum et ses généralisations. Pour atteindre cet objectif, nous avons développé une approche de recherche tabou adaptative multistart pour le problème de clique maximum classique, un algorithme recherche tabou multi-voisinage pour la clique maximum de sommets pondérés, et une méthode métaheuristique hybride pour le problème de la clique maximum d-arêtes pondérés. En outre, nous appliquons ces méthodes heuristiques développées pour résoudre ces problèmes difficiles qui sont étroitement liés au problème de la clique maximum. Tous les algorithmes sont mis en oeuvre et testés avec succès sur un certain nombre de cas de référence provenant de divers domaines d-application. Les méthodes proposées concurrencent favorablement les autres approches de l-état de l-art.

en fr

Keywords : Maximum clique problem Graph coloring problem Sum coloring problem Tabu search Constrained neighborhood

Mots-clés : Problème de la clique maximum Problème de coloration de graphe Problème de Somme coloration Recherche tabou Contraint de voisinage





Autor: Qinghua Wu -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados