Littérature scientifique sur le sujet « Arbre couvrant de poids minimal »

Dans cette thèse, nous étudions le problème de l’Interdiction de l’Arbre Couvrant Minimal (IACM). Ce problème est un jeu à deux joueurs entre un opérateur de réseau et un interdicteur. Le premier détermine un Arbre Couvrant Minimal (ACM) dans un réseau. Limité par un budget, le second cherche à changer la topologie du réseau pour augmenter le poids de l’ACM. Deux types d’interdiction sont considérés : l’interdiction totale et l’interdiction partielle.Une arête totalement interdite est considérée comme absente tandis que le poids d’une arête partiellement interdite est augmentée d’une quantité prédéfinie. Le budget de l’interdicteur est modélisé par une contrainte de cardinalité,chaque arête a le même poids d’interdiction, ou une contrainte de sac `a dos, les poids d’interdiction peuvent être différents. Sept formulations mathématiques du problème IACM ont été élaborées. Elles se sont avérées efficaces pour des graphes de petite et moyenne taille. Un algorithme de type ”Branch-and-Price” et un algorithme basé sur la décomposition de Benders ont été conçus pour les graphes de plus grande taille. En outre, des inégalités valides sont proposées pour renforcer les modèles et améliorer les performances des algorithmes. Des instances de 200sommets et 19900 ar êtes ont ainsi pu être résolues optimalement
In this thesis, we study the Minimum Spanning Tree Interdiction (MSTI) problem. This problem is a two-player game between a network operator and an interdictor. The former aims to determine a Minimum Spanning Tree (MST) in a network. Constrained by a budget, the latter seeks to change the network topology to increase the weight of aMST. Two types of interdiction are considered: total and partial interdiction. A total interdicted edge is considered absent while the weight of a partial interdicted edge is augmented by a predefined amount. The interdictor’s budget ismodeled as a cardinality, each edge has the same interdiction weight, or knapsack constraint, the interdiction weightsmight be different. Seven mathematical formulations for the MSTI problem are devised. They proved to be efficient on small and medium-size graphs. A Branch-and-Price algorithm and a Benders Decomposition algorithm are designedfor larger graphs. In addition, valid inequalities are proposed to strengthen the models and improve the efficiency of the proposed methods. Instances including up to 200 nodes and 19900 edges are solved to optimality

De nos jours la protection des données numériques est un problème très important. Que ce soit pour des applications de confidentialité, de communication, de traçabilité ou d'identification par exemple, il est nécessaire de développer des techniques adaptées. Dans le cadre de cette thèse en collaboration avec la société STRATEGIES S.A., la méthode choisie pour la protection de maillages 3D est l'insertion de données cachées, également appelée tatouage numérique. Pour des données 3D, un des problèmes les plus importants est la phase de synchronisation qui intervient dans les algorithmes d'insertion et d'extraction des données. Cette phase permet de repérer, de sélectionner et d'ordonner les « zones » qui sont privilégiées pour la dissimulation d'information. Nous avons choisi d'orienter le manuscrit sur cette phase. Ainsi, nous proposons une classification des méthodes de tatouages en fonction de leur méthode de synchronisation. Puis en se basant sur des techniques de synchronisation par des structures de données, telle que les arbres couvrants de poids minimum, nous proposons une analyse théorique de cette structure. Dans un premier temps nous expliquons les raisons de la sensibilité des arbres à la mobilité des points. Puis connaissant ses faiblesses, nous proposons une autre technique de synchronisation toujours basée sur les arbres couvrants de poids minimum
Data security is one of the main issue in computer science. We need to develop solutions for confidentiality, communication, fingerprinting or identification applications for exemple. In this thesis made with STRATEGIES S.A., the chosen method to protect 3D meshes is watermarking.Watermarking is divided in two steps, the embedding and the extraction. In both of them a synchronization phase is needed. It is one of the most important step for 3D mesh because it permits to look for areas available to embed information, and order them. All the thesis is devoted to the synchronization step. First of all, we propose a classification of watermarking techniques based on the type of synchronization method instead of evaluation criterions such as robustness or capacity.Then, from methods based on Euclidean minimum spanning tree, we propose a theoritical analysis of the mobility of the vertices in that kind of structure. First, we explain the reasons of the sensibility of the structure. Secondly, we propose another scheme based on the Euclidean minimum spanning tree knowing its fragility

Cette thèse s'inscrit dans le cadre de l'évolution des Systèmes d'Informations Géographiques (SIG) et de leur capacité à répondre à des problématiques environnementales qui s'expriment de manière globale et transversale. Dans un contexte ou l'information géographique est en plein essor et où la quantité de données disponible ne cesse de croitre, le besoin en terme d'outil d'aide a la décision n'a jamais été aussi fort. Cette étude s'attache tout particulièrement au cadre de la résolution de problématiques liées à l'eau et l'environnement lorsque les données deviennent trop volumineuses pour être traitées par des moyens de calculs séquentiels classiques. Nous proposons une plateforme de calculs répartis sur une grappe d'ordinateurs qui parallélise le calcul de la délimitation des bassins versants des grands fleuves et la détermination des flots d'accumulation. A cette fin nous introduisons une technique de calcul parallèle d'une forêt d'arbres couvrants minimums représentant le parcours de l'eau de chaque point du Modèle Numérique de Terrain (MNT) vers la mer. Cette technique débute par une délimitation des cuvettes (ensemble de points allant vers le même minimum local) contenues dans le MNT. Ensuite une hiérarchie de déversement des cuvettes les unes dans les autres est construite jusqu'à obtenir les bassins versants des fleuves. L'étude se poursuit par la description d'un algorithme parallèle pour le calcul très couteux des flots d'accumulation en chaque point du MNT. Enfin cette thèse présente une version ≪out-of-core≫ de nos algorithmes parallèles afin d'étendre la portée de nos travaux a des grappes de dimensions modestes qui ne peuvent pas charger en mémoire la totalité du MNT traite.

On s'attache dans cette thèse à plusieurs aspects liés à la résolution de problèmes multi-objectifs, sans se limiter au cas biobjectif. Nous considérons la résolution exacte, dans le sens de la détermination de l'ensemble des points non dominés, ainsi que la résolution approchée dans laquelle on cherche une approximation de cet ensemble dont la qualité est garantie a priori.Nous nous intéressons d'abord au problème de la détermination d'une représentation explicite de la région de recherche. La région de recherche, étant donné un ensemble de points réalisables connus, exclut la partie de l'espace des objectifs que dominent ces points et constitue donc la partie de l'espace des objectifs où les efforts futurs doivent être concentrés dans la perspective de déterminer tous les points non dominés.Puis nous considérons le recours aux algorithmes de séparation et évaluation ainsi qu'aux algorithmes de ranking afin de proposer une nouvelle méthode hybride de détermination de l'ensemble des points non dominés. Nous montrons que celle-ci peut également servir à obtenir une approximation de l'ensemble des points non dominés. Cette méthode est implantée pour le problème de l'arbre couvrant de poids minimal. Les quelques propriétés de ce problème que nous passons en revue nous permettent de spécialiser certaines procédures et d'intégrer des prétraitements spécifiques. L'intérêt de cette approche est alors soutenu à l'aide de résultats expérimentaux
This thesis deals with several aspects related to solving multi-objective problems, without restriction to the bi-objective case. We consider exact solving, which generates the nondominated set, and approximate solving, which computes an approximation of the nondominated set with a priori guarantee on the quality.We first consider the determination of an explicit representation of the search region. The search region, defined with respect to a set of known feasible points, excludes from the objective space the part which is dominated by these points. Future efforts to find all nondominated points should therefore be concentrated on the search region.Then we review branch and bound and ranking algorithms and we propose a new hybrid approach for the determination of the nondominated set. We show how the proposed method can be adapted to generate an approximation of the nondominated set. This approach is instantiated on the minimum spanning tree problem. We review several properties of this problem which enable us to specialize some procedures of the proposed approach and integrate specific preprocessing rules. This approach is finally supported through experimental results