Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação. / This dissertation studies the minimum cost k-tree problem (kMST): given a connected graph G, a nonnegative cost function c_e for each edge e and a positive integer k, find a minimum cost tree with k vertices. The kMST is an NP-hard problem, which implies that it is not known a polynomial algorithm to solve it. In this dissertation we discuss some cases that can be solved in polynomial time. We also study approximation algorithms for the kMST. Among the approximation algorithms we present the 2-approximation developed by Naveen Garg, which is currently the algorithm with the best approximation factor.

Energy is a limited source in wireless sensor networks and in most applications, it is non-renewable / so designing energy-effcient communication patterns is very important. In this thesis, we de

Η εύρεση γεννητικών δέντρων ελάχιστου-κόστους αποτελεί ένα κλασικό επιστημονικό πρόβλημα με σημαντικές εφαρμογές στη σχεδίαση δικτύων. Δοθέντος ενός γραφήματος, όπου κάθε πλευρά σχετίζεται με ένα βάρος (κριτήριο) το πρόβλημα της εύρεσης ενός Ελάχιστου Γεννητικού Δέντρου ανέρχεται στο πρόβλημα της εύρεσης ενός γεννητικού δέντρου με το ελάχιστο συνολικό κόστος. Το πρόβλημα ΕΓΔ έχει αποτελέσει αντικείμενο ενδιαφέροντος πολλών μελετητών με αποτέλεσμα την ανάπτυξη αλγορίθμων πολυωνυμικού-χρόνου, όπως είναι ο αλγόριθμος του Prim, του Sollin και του Kruskal. Στον πραγματικό κόσμο όμως υπάρχουν περιπτώσεις όπου πρέπει να λάβουμε ταυτόχρονα υπόψη πολλά κριτήρια προκειμένου να καθορίσουμε ένα ΕΓΔ. Αυτό συμβαίνει γιατί κάθε πλευρά του γραφήματος σχετίζεται με παραπάνω από ένα κόστη. Για παράδειγμα, στη σχεδίαση ενός τηλεπικοινωνιακού δικτύου, πέρα από το κόστος κατασκευής των συνδέσεων μεταξύ των πόλεων ή των τερματικών μας ενδιαφέρουν και άλλοι παράγοντες. Ο χρόνος που απαιτείται για την κατασκευή, η δυσκολία και πολυπλοκότητα της κατασκευής, η καθυστέρηση μετάδοσης της πληροφορίας αλλά και η αξιοπιστία του συστήματος αποτελούν σημαντικούς παράγοντες που πρέπει να ληφθούν υπόψη στην σχεδίαση του δικτύου. Αλλά και στην καθημερινή ζωή, πολλές φορές χρειάζεται να ληφθούν σημαντικές αποφάσεις οι οποίες εξαρτώνται από περισσότερα από ένα κριτήρια. Παραδείγματος χάριν, άνθρωποι που ταξιδεύουν θέλουν να βελτιστοποιήσουν τη διανυόμενη απόσταση, το κόστος, και το χρόνο μετακίνησης. Το ζητούμενο είναι πως μπορεί να οδηγηθεί κανείς στη λήψη μιας βέλτιστης για αυτόν απόφασης, που κάτω από δεδομένες συνθήκες μπορεί να είναι περισσότερες από μία. Δηλαδή, δεν οδηγούμαστε σε μία μοναδική βέλτιστη λύση αλλά σε ένα σύνολο από «βέλτιστες» λύσεις και ο ενδιαφερόμενος, ανάλογα με τα ιδιαίτερα χαρακτηριστικά του προβλήματος, κάνει την τελική επιλογή. Το πρόβλημα ΕΓΔ, στο οποίο ζητείται η ελαχιστοποίηση περισσοτέρων του ενός κριτηρίων είναι γνωστό ως το πρόβλημα ΕΓΔ πολλαπλών κριτηρίων (multi-criteria minimum spanning tree problem). Η συνεισφορά της παρούσας διπλωματικής λοιπόν αποτελείται από δύο μέρη: Το πρώτο, εστιάζεται στην κριτική επισκόπηση και περιγραφή των υπαρχόντων μεθόδων επίλυσης του προβλήματος ΕΓΔ δύο κριτηρίων. Το δεύτερο, αφορά την υλοποίηση και πειραματική αξιολόγηση δύο βασικών αλγορίθμων για την επίλυση του εν λόγω προβλήματος. Συγκεκριμένα, υλοποιήθηκε η τροποποιημένη εκδοχή (για το πρόβλημα ΕΓΔ πολλαπλών κριτηρίων) του αλγορίθμου του Prim καθώς και μία προσεγγιστική μέθοδος επίλυσης του προβλήματος ΕΓΔ πολλαπλών κριτηρίων. / The minimum spanning tree problem (MST) is of high importance in network optimization. Given a connected graph G where each edge has a weight, the goal is to find the spanning tree with the least cost among all spanning trees of G. Due to its many practical applications, the MST problem has been studied in depth and many efficient polynomial-time algorithms have been developed by Sollin, Kruskal, Prim etc. But in real life, there cases where one has to take simultaneously into consideration many criteria in order to determine a MST because there are multiple weights defined on each edge of the graph. For example, when designing the layout of a telecommunication network, besides the cost for connections between cities or terminals we are interested in other factors too. The time for communication and construction, the difficulty of the construction or the reliability of the system are also important factors and need to be taken into consideration. But also in everyday life, in many cases we need to take decisions that depend on multiple criteria. For instance, people who travel want to minimize simultaneously the cost, the distance and the time. The problem is that in these cases there is not only one optimal solution but rather a set of optimal solutions and the decision maker depending on the characteristics of each case will make the final call. The MST problem in which we want to minimize more than one criteria is known as the multi-criteria minimum spanning tree problem. The contribution of this thesis is composed of two parts. The first part focuses on the critical survey and description of various methods for solving the bi-criteria case of the MST problem. The other part focuses on the implementation and the experimental evaluation of two known and important algorithms. More precisely, we have implemented the modified version of the Prim’s algorithm (for the multi-criteria MST problem) and one approximate algorithm as proposed by Hamacher & Ruhe.

Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:<br/> <strong>Arbres aléatoires uniformes.</strong> Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.<br/> <strong>Graphes aléatoires.</strong> J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. <strong>Arbres couvrant minimaux.</strong> J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.

Image segmentation is an important research area in digital image processing with several applications in vision-guided autonomous robotics, product quality inspection, medical diagnosis, the analysis of remotely sensed images, etc. The aim of image segmentation can be defined as partitioning an image into homogeneous regions in terms of the features of pixels extracted from the image. Image segmentation methods can be classified into four main categories: 1) clustering methods, 2) region-based methods, 3) hybrid methods, and 4) bayesian methods. In this thesis, major image segmentation methods belonging to first three categories are examined and tested on typical images. Moreover, improvements are also proposed to well-known Recursive Shortest-Spanning Tree (RSST) algorithm. The improvements aim to better model each region during merging stage. Namely, grayscale histogram, joint histogram and homogeneous texture are used for better region modeling.

Le modèle du tas de sable est un modèle de diffusion discret et isotrope introduit par les physiciens Bak, Tang et Wiesenfeld comme illustration de la criticalité auto-organisée. Pour tout graphe, souvent supposé fini, Dhar a formalisé de nombreuses propriétés simplifiant son analyse. Cette thèse propose des études de ce modèle sur la grille bidimensionnelle usuelle et certains de ses sous-graphes également infinis que sont les bandes bi-infinies de hauteur finie. Des approximations du comportement de la pile de sable peuvent se rapprocher de certains modèles de bootstrap percolation avec un support de stabilisation rectangulaire. Les lois sur son demi-périmètre peuvent se décrire à l’aide de statistiques sur les permutations. Un sous-produit de ce travail fait apparaître une différence de deux séries génératrices comptant des permutations selon deux statistiques mahoniennes classiques dont est extrait un polynôme à coefficients entiers et surtout positifs. La suite de cette thèse revisite dans le cadre de ces graphes infinis, des structures jusque-là bien définies uniquement dans le cas des graphes finis, notamment la récurrence. Dans le modèle sur une bande de hauteur finie H, l’existence donnée par Járai et Lyons d’automates finis reconnaissant les configurations récurrentes lues colonne par colonne est étendu par une construction explicite d’automates avec un nombre moindre d’états, se rapprochant de la conjecture de Gamlin. Dans une seconde approche, l’étude se concentre sur les configurations sur la grille entière qui sont périodiques dans les deux directions. Le puits, un sommet du graphe garantissant la terminaison de la stabilisation, est placé à l’infini dans une direction de pente rationnelle. Ceci permet à la fois de préserver la bipériodicité et de proposer une forme affaiblie du critère de Dhar caractérisant ainsi par un algorithme effectif les configurations récurrentes. Ces configurations récurrentes bipériodiques sont des candidates naturelles pour être les éléments de sous-groupes finis de l’éventuel groupe du tas de sable sur la grille. Des éléments de construction de cette loi de groupe donnent expérimentalement quelques sous-groupes finis. / The sandpile model is a discrete model for diffusion of grains on a graph introduced by physicists Bak, Tang and Wiesenfeld as an illustration for self-organised criticality. For any finite graph, Dhar identified many of its numerous structures which simplify its analysis. This thesis focus on the usual square lattice and its subgraphs which are strips of height H, both notions of infinite graphs. Approximations on the behaviour of the stabilisation of a large stack of grains at the origin of the square lattice lead to some random distribution of grains, which stabilisation is connected to some models of bootstrap percolation where modified vertices by this stabilisation forms a rectangle. The laws of the half-perimeter of this rectangle are described by statistics on permutations. As a byproduct, the difference between the generating functions over some permutations of two classical mahonian statistics on permutations appears to mainly be a polynomial with coefficients which are integers and especially positive. Then, this thesis visits in the case of the studied infinite graphs some well-defined structures on finite graphs, in particular the recurrence. In the model on an horizontal strip of height H, we extend the existence of finite automata recognizing recurrent configurations read column by column presented by Járai and Lyons to new automata with significantly less states and these numbers are closer to a conjecture due to Gamlin. An implementation leads to explicit automata for heights 3 and 4 while up to now only the case 2 was obtained by hand. In a second approach, we consider the configurations on the twodimensional square lattice which are periodic in two directions. We suggest to place the sink ensuring that the stabilisation ends at infinity in a direction of rational slope which allows to preserve biperiodicity and a weaker form of Dhar criterion for recurrent configurations. Hence we obtain an effective algorithm defining recurrent configurations among the biperiodic and stable configurations. These biperiodic and recurrent configurations are natural candidates for being the elements of finite subgroups of the hypothetical group on configurations of the sandpile model on the square lattice. We discuss some notions allowing the definition of the law of such a group and experimentally provide some finite subgroups.

This masters'sthesis deals with graph theory and utilization of this theory for design and optimization of data network structures. Introduction chapter describes graph theory in general view, i.e. fundamental terms used for graph description, graph distinguishing, etc. Next part describes graph algorithms, for example a shortest path finding. After this I write about actual routing protocols where the graph algorithms are used. Last but one part deals with queuing theory and final part describes practical presentation of using graph theory for design and optimization of data network structure in Matlab programme environment.

Les réseaux de capteurs sont des réseaux particuliers composés d'objets contraints en ressources. Ils possèdent une faible puissance de calcul, une faible puissance de transmission, une faible bande passante, une mémoire de stockage limitée ainsi qu'une batterie à durée de vie limitée. Afin d'intégrer de tels réseaux dans l'internet des objects, de nouveaux protocoles ont été standardisés. Parmi ces protocoles, le protocole RPL (pour Routing Protocol for Low Power and Lossy Networks). Ce protocole est destiné a construire une topologie logique de routage appelée DODAG. Dans cette thèse, nous abordons l'aspect acheminement de données qui considère une topologie de routage arborescente. L'acheminement des données se fait donc de saut en saut d'un enfant à son parent (ou d'un parent à son enfant). Optimiser la construction du DODAG revient donc à construire un arbre couvrant selon une contrainte donnée. Un arbre couvrant est une structure communicante qui permet de maintenir un unique chemin entre toutes paires de noeuds tout en minimisant le nombre de liens de communication utilisés. De plus, nous considérons les contraintes des réseaux de capteurs telles qu'une batterie déchargée et la variabilité du lien radio comme des fautes transitoires. Ceci nous conduit par conséquent à construire une structure couvrante tolérante aux fautes transitoires. L'auto-stabilisation est une branche de l'algorithmique distribuée qui assure qu'à la suite d'une ou de plusieurs fautes transitoires, le système va retrouver de lui-même un comportement correcte au bout d'un temps fini. L'objectif de cette thèse est de proposer des algorithmes auto-stabilisants dédiés aux réseaux de capteurs. / Spanning Trees from theory to practiceSelf-Stabilizing algorithms and sensor networksAbstract : Sensor networks are composed of ressources constrained equipments. They have low computing power, low transmission power, low bandwidth, limited storage memory and limited battery life.In order to integrate such networks in the Internet of things, new protocols were standardized such as RPL protocol (for Routing Protocol for Low Power and Lossy Networks). This protocol is intended to build a logical routing topology called DODAG (for Destination Oriented Directed Acyclic Graph). In this thesis, we discuss the data routing aspect by considering a tree routing topology. Thus, the routing of data is hop by hop from a child to its parent (or from a parent to its child). Optimize the construction of the DODAG is therefore to build a spanning tree in a given constraint. A spanning tree is a connecting structure that maintains a unique path between all pairs of nodes while minimizing the number of used communication links. Furthermore, we consider the constraints of sensor networks, such as a dead battery and the variability of the radio link as transient faults. This leads us to build a covering structure tolerant to transient faults. The self-stabilization is a branch of distributed algorithms that ensures that following one or more transient faults, the system will find itself a correct behavior after a finite time.The objective of this thesis is to propose self-stabilizing algorithms dedicated to sensor networks. The contributions of this thesis are:In the first part of the thesis, we proposed a self-stabilizing algorithm for the construction of a minimum diameter spanning tree.This construction is natural when we want to minimize the communication delay between a root and all other network nodes. Our algorithm has several advantages. First, our algorithm is limited to memory occupation of O(log n) bits per node, reducing the previous result of an n factor while maintaining a polynomial convergence time. Then, our algorithm is the first algorithm for minimum diameter spanning tree that works as an unfair distribution demon. In other words, we make no restriction on the asynchronous network behavior. In the second part of the thesis, we are interested in the unstable topology built by RPL protocol (DODAG). Our solution is to place an additional constraint on the number of children a node can accept during the construction of the DODAG. This constraint has the effect of reducing the rate of parent change and consequently to improve the protocol performance in terms of packet delivery rate, delay of communication and power consumption. In addition, we implemented a mechanism to update the information of the downward routes in RPL. Furthermore, our solution has the advantage of not generating overhead because we use existing control messages provided by RPL to implement it. Finally, this contribution is twofold since we validated our solution both by simulations and experiments.

No description available.

No description available.