Heuristiques efficaces pour le probleme de partitionnement de graphe

These last years, the graph partitioning problem attracts the attention of many of researchers considering the increase of its applications in various domains. The problem consists in partitioning the vertices of a graph in roughly equal parts, such that the number of edges connecting vertices from different partitions is minimized.; The graph partitioning problem is NP-hard. The graph size in this problem reaches several hundreds of thousand of vertices (even several millions), thus making it a very complex problem. Several heuristics has been developed to find it a reasonable approximation. The majority of these heuristics are based on the multilevel approach. The basic idea of this approach consists in reducing the complexity of the problem by decreasing, in an iterative way, the size of the graph. We produce an initial partition of the most reduced graph which we then project on the original graph.; In this report, we present new heuristics, for the graph partitioning problem. After various comparisons with the best known results of reference graphs, we show that our algorithms produce better partitions than the one produced by the most powerful algorithms found in the literature.