Download or read book Contributions À Des Problèmes de Partitionnement de Graphe Sous Contraintes de Ressources written by Dang Phuong Nguyen and published by . This book was released on 2016 with total page 0 pages. Available in PDF, EPUB and Kindle. Book excerpt: The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes.....