Dissertations / Theses: 'Graph algorithmic'

1

Bessy, Stéphane. "Some problems in graph theory and graphs algorithmic theory." Habilitation à diriger des recherches, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00806716.

Full text

Abstract:

This document is a long abstract of my research work, concerning graph theory and algorithms on graphs. It summarizes some results, gives ideas of the proof for some of them and presents the context of the different topics together with some interesting open questions connected to them The first part precises the notations used in the rest of the paper; the second part deals with some problems on cycles in digraphs; the third part is an overview of two graph coloring problems and one problem on structures in colored graphs; finally the fourth part focus on some results in algorithmic graph theory, mainly in parametrized complexity.

APA, Harvard, Vancouver, ISO, and other styles

2

Kanté, Mamadou Moustapha. "Graph structurings : some algorithmic applications." Thesis, Bordeaux 1, 2008. http://www.theses.fr/2008BOR13693/document.

Full text

Abstract:

Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La largeur de rang, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de vertex-minor pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure comme vertex-minor. Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété P dans un graphe G, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si G satisfait P en n'utilisant que les étiquettes des sommets. Nous montrons que si P est une propriété définissable en logique du premier ordre alors, certaines classes de graphes de largeur de clique localement bornée admettent un système d'étiquetage pour P avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire. Si x et y sont deux sommets, X un ensemble de sommets et F un ensemble d'arêtes, nous notons Conn(x,y,X,F) la propriété qui vérifie dans un graphe donné si x et y sont connectés par un chemin, qui ne passe par aucun sommet de X si aucune arête de F. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que Conn(x,y,X,0) admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des combinaisons de graphes qui ont une petite largeur de clique et telles que le graphe d'intersection de ces derniers est planaire et est de degré borné
Every property definable in onadic second order logic can be checked in polynomial-time on graph classes of bounded clique-width. Clique-width is a graph parameter defined in an algebraical way, i.e., with operations ``concatenating graphs'' and that generalize concatenation of words.Rank-width, defined in a combinatorial way, is equivalent to the clique-width of undirected graphs. We give an algebraic characterization of rank-width and we show that rank-width is linearly bounded in term of tree-width. We also propose a notion of ``rank-width'' of directed graphs and a vertex-minor inclusion for directed graphs. We show that directed graphs of bounded ``rank-width'' are characterized by a finite list of finite directed graphs to exclude as vertex-minor. Many graph classes do not have bounded rank-width, e.g., planar graphs. We are interested in labeling schemes on these graph classes. A labeling scheme for a property P in a graph G consists in assigning a label, as short as possible, to each vertex of G and such that we can verify if G satisfies P by just looking at the labels. We show that every property definable in first order logic admit labeling schemes with labels of logarithmic size on certain graph classes that have bounded local clique-width. Bounded degree graph classes, minor closed classes of graphs that exclude an apex graph as a minor have bounded local clique-width. If x and y are two vertices and X is a subset of the set of vertices and Y is a subset of the set of edges, we let Conn(x,y,X,Y) be the graph property x and y are connected by a path that avoids the vertices in X and the edges in Y. This property is not definable by a first order formula. We show that it admits a labeling scheme with labels of logarithmic size on planar graphs. We also show that Conn(x,y,X,0) admits short labeling schemes with labels of logarithmic size on graph classes that are ``planar gluings'' of graphs of small clique-width and with limited overlaps

APA, Harvard, Vancouver, ISO, and other styles

3

Rocha, Leonardo Sampaio. "Algorithmic aspects of graph colouring heuristics." Nice, 2012. https://tel.archives-ouvertes.fr/tel-00759408.

Full text

Abstract:

Une coloration propre d’un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que deux sommets voisins ont des couleurs distinctes. Les colorations permettent de modéliser des problèmes d’ordonnancement, d’allocation de fréquences ou de registres. Le problème de trouver une coloration propre d’un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d’évaluer quelques heuristiques pour le problème d’e la coloration propre. Nous commençons par dresser un état de l’art des résultats sur ces deux paramètres. Puis nous montrons que déterminer le nombre de Grundy est NP-difficile pour un graphe cordal et polynomial sur le graphe sans P5 bipartis. Ensuite nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. Nombre b-chromatique) et en particulier, nous montrons que décider sir le nombre de Grundy (ou le nombre b-chromatique) d’un graphe G est au moins V(G)-k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d’un graphe
A proper coloring of a graph is a function that assigns a color to each vertex with the restriction that adjacent vertices are assigned with distinct colors. Proper colorings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper coloring of a graph with the minimum number of colors is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colorings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy Number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number or a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and p4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least V(G)-k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameter of a graph

APA, Harvard, Vancouver, ISO, and other styles

4

De, Lara Nathan. "Algorithmic and software contributions to graph mining." Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAT029.

Full text

Abstract:

Depuis l'invention du PageRank par Google pour les requêtes Web à la fin des années 1990, les algorithmes de graphe font partie de notre quotidien. Au milieu des années 2000, l'arrivée des réseaux sociaux a amplifié ce phénomène, élargissant toujours plus les cas d'usage de ces algorithmes. Les relations entre entités peuvent être de multiples sortes : relations symétriques utilisateur-utilisateur pour Facebook ou LinkedIn, relations asymétriques follower-followee pour Twitter, ou encore, relations bipartites utilisateur-contenu pour Netflix ou Amazon. Toutes soulèvent des problèmes spécifiques et les applications sont nombreuses : calcul de centralité pour la mesure d'influence, le partitionnement de nœuds pour la fouille de données, la classification de nœuds pour les recommandations ou l'embedding pour la prédiction de liens en sont quelques exemples.En parallèle, les conditions d'utilisation des algorithmes de graphe sont devenues plus contraignantes. D'une part, les jeux de données toujours plus gros avec des millions d'entités et parfois des milliards de relations limite la complexité asymptotique des algorithmes pour les applications industrielles. D'autre part, dans la mesure où ces algorithmes influencent nos vies, les exigences d'explicabilité et d'équité dans le domaine de l'intelligence artificielle augmentent. Les algorithmes de graphe ne font pas exception à la règle. L'Union européenne a par exemple publié un guide de conduite pour une IA fiable. Ceci implique de pousser encore plus loin l'analyse des modèles actuels, voire d'en proposer de nouveaux.Cette thèse propose des réponses ciblées via l'analyse d'algorithmes classiques, mais aussi de leurs extensions et variantes, voire d'algorithmes originaux. La capacité à passer à l'échelle restant un critère clé. Dans le sillage de ce que le projet Scikit-learn propose pour l'apprentissage automatique sur données vectorielles, nous estimons qu'il est important de rendre ces algorithmes accessibles au plus grand nombre et de démocratiser la manipulation de graphes. Nous avons donc développé un logiciel libre, Scikit-network, qui implémente et documente ces algorithmes de façon simple et efficace. Grâce à cet outil, nous pouvons explorer plusieurs tâches classiques telles que l'embedding de graphe, le partitionnement, ou encore la classification semi-supervisée
Since the introduction of Google's PageRank method for Web searches in the late 1990s, graph algorithms have been part of our daily lives. In the mid 2000s, the arrival of social networks has amplified this phenomenon, creating new use-cases for these algorithms. Relationships between entities can be of multiple types: user-user symmetric relationships for Facebook or LinkedIn, follower-followee asymmetric ones for Twitter or even user-content bipartite ones for Netflix or Amazon. They all come with their own challenges and the applications are numerous: centrality calculus for influence measurement, node clustering for knowledge discovery, node classification for recommendation or embedding for link prediction, to name a few.In the meantime, the context in which graph algorithms are applied has rapidly become more constrained. On the one hand, the increasing size of the datasets with millions of entities, and sometimes billions of relationships, bounds the asymptotic complexity of the algorithms for industrial applications. On the other hand, as these algorithms affect our daily lives, there is a growing demand for explanability and fairness in the domain of artificial intelligence in general. Graph mining is no exception. For example, the European Union has published a set of ethics guidelines for trustworthy AI. This calls for further analysis of the current models and even new ones.This thesis provides specific answers via a novel analysis of not only standard, but also extensions, variants, and original graph algorithms. Scalability is taken into account every step of the way. Following what the Scikit-learn project does for standard machine learning, we deem important to make these algorithms available to as many people as possible and participate in graph mining popularization. Therefore, we have developed an open-source software, Scikit-network, which implements and documents the algorithms in a simple and efficient way. With this tool, we cover several areas of graph mining such as graph embedding, clustering, and semi-supervised node classification

APA, Harvard, Vancouver, ISO, and other styles

5

Wolff, Tanya Layng. "Cayley networks, group, graph theoretic and algorithmic properties." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq22426.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Tamura, Takeyuki. "Graph Algorithmic Approaches for Structure Inferences in Bioinformatics." 京都大学 (Kyoto University), 2006. http://hdl.handle.net/2433/68893.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Jaeger, Mordechai. "An algorithmic approach to center location and related problems." Diss., The University of Arizona, 1992. http://hdl.handle.net/10150/185767.

Full text

Abstract:

Center location on cactus graphs. The p-center problem has been shown to be NP-hard for case of a general graph, yet polynomial algorithms exist for the case of a tree graph. Specifically, we consider "cactus graphs" where each edge is contained in at most one cycle. We show that the p-center problem on this class can be solved in polynomial time using a decomposition algorithm. We partition the graph into a set of subgraphs which are then solved sequentially. The solutions to the subgraphs are linked by a single parameter. The algorithm runs in polynomial time. Locating capacity limited centers on trees. The uncapacitated p-center problem on trees is solvable in polynomial time. We extend this result to include the case where each center can serve a limited number of customers and show that the capacitated p-center on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. Center location on spheres. We discuss the unweighted center location problem. The following results are presented: (i) An O(n) time algorithm to solve the 1-center problem if the vertices are on one half of the sphere, and an O(n) time algorithm to check whether this condition holds. Both algorithms are based on presenting the problems as 3-dimensional convex programming problems with linear constraints and applying a pruning technique to find the optimum in O(n) time. (ii) An O(n$\sp3$ log n) time algorithm for the 2-center problem on the whole sphere. (iii) A reduction to show that the general p-center problem on a sphere is NP-hard. Locating hyperplanes on hypercubes. In linear regression models we are interested in locating a (d-1) dimensional hyperplane that will be as "close" as possible to existing vertices in the d-dimensional hypercube. The least squares criterion is usually applied for the linear fitting problem; while fitting according to the least absolute value ("minisum") seems to be "complicated". We solve fitting problems with the minisum criterion and present linear time algorithms when the dimension d is fixed. (Abstract shortened with permission of author.)

APA, Harvard, Vancouver, ISO, and other styles

8

Pandey, Arti. "Algorithmic aspects of domination and its variations." Thesis, IIT Delhi, 2016. http://localhost:8080/xmlui/handle/12345678/7038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Thiebaut, Jocelyn. "Algorithmic and structural results on directed cycles in dense digraphs." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS059.

Full text

Abstract:

Dans cette thèse, nous nous intéressons à quelques problèmes algorithmiques et structurels du packing de cycles (orientés) dans les graphes orientés denses. Ces problèmes sont notamment motivés par la compréhension de la structure de tels graphes, mais également car de nombreux problèmes algorithmiques sont faciles (résolubles en temps polynomial) sur des graphes orientés acycliques alors qu'il sont NP-difficiles sur les graphes orientés en général.Plus spécifiquement, nous étudions dans un premier temps le packing de cycles et le packing de triangles dans les tournois. Ces problèmes sont les duaux (d'un point de vue programmation linéaire) des problèmes de feedback arc/vertex set qui ont reçu beaucoup d'attention dans la littérature. Nous montrons entre autres qu'il n'y a pas d'algorithme polynomial pour trouver une collection maximale de cycles (respectivement triangles) sommet ou arc-disjointe dans les tournois, sauf si P = NP. Nous nous intéressons également aux algorithmes d'approximations et de complexité paramétrée de ces différents problèmes.Nous étudions ensuite plus en détail ces problèmes dans le cas spécifique où le tournoi admet un feedback arc set qui est un couplage, appelé sparse. Étonnamment, le problème reste difficile dans le cas des triangles sommet-disjoints, mais devient polynomial pour les triangles et cycles arc-disjoints. Ainsi, nous explorons l'approximation et la complexité paramétrée du cas sommet-disjoints dans les tournois sparses.Enfin, nous répondons positivement à une conjecture structurelle sur les bipartis complets k-réguliers par Manoussakis, Song et Zhang datant de 1994. En effet, nous démontrons que tous les digraphes de cette classe non isomorphes à un digraphe particulier possèdent pour tout p pair avec 4 leq p leq |V(D)| - 4 un cycle C de taille p tel que D V(C) est hamiltonien
In this thesis, we are interested in some algorithmic and structural problems of (oriented) cycle packing in dense digraphs. These problems are mainly motivated by understanding the structure of such graphs, but also because many algorithmic problems are easy (i.e. resolvable in polynomial time) on acyclic digraphs while they are NP-difficult in the general case.More specifically, we first study the packing of cycles and the packing of triangles in tournaments. These problems are the two dual problems (from a linear programming point of view) of feedback arc/vertex set that have received a lot of attention in literature. Among other things, we show that there is no polynomial algorithm to find a maximum collection of cycles (respectively triangles) vertex or arc-disjoint in tournaments, unless P = NP. We are also interested in algorithms of approximations and parameterized complexity of these different problems.Then, we study these problems in the specific case where the tournament admits a feedback arc set which is a matching. Such tournaments are said to be sparse. Surprisingly, the problem remains difficult in the case of vertex-disjoint triangles, but the packing of triangles and the packing of arc-disjoint cycles become polynomial. Thus, we explore the approximation and parameterized complexity of the vertex-disjoint case in sparse tournaments.Finally, we answer positively to a structural conjecture on k-regular bipartite tournaments by Manoussakis, Song and Zhang from 1994. Indeed, we show that all digraphs of this non-isomorphic class to a particular digraph have for every p even with 4 leq p leq |V(D)| - 4 a C cycle of size p such that D V(C) is Hamiltonian

APA, Harvard, Vancouver, ISO, and other styles

10

Kalzi, Hasan. "Graph Complexity Based on a Heuristic That Involves the Algorithmic Complexity Behaviour of Multiplex Networks on Graphs." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-302104.

Full text

Abstract:

Since determining the complexity of multiplex networks is an NP-hard problem, I decided to calculate the complexity of graphs using heuristics. I am the first in this path who did these kinds of calculations. I always wanted to define complexity as a mathematical characteristic in the structure of graphs. This investigation explores the behaviour of the algorithmic complexity of multiplex networks on graphs to discover if it is possible to extract a mathematical expression that can represent it. If we obtain a mathematical representation for graph complexity, we tackle this problem from the NP-hard problem area. It also can be used as one of the characteristics of the graph, e.g., the number of nodes, edges, or motifs of a specific size. Santoro and Nicosia, in their research, obtained the algorithmic complexity of multiplex networks is defined [1]. Thus, an approach that uses a heuristic strategy can be the easiest way to get near an optimal mathematical definition of the complexity of graphs. In this thesis, I re-introduce the recent representation of the algorithmic complexity [2] for multiplex networks from an algorithmic information theory [ 3 ] perspective. This definition depends mainly on Kolmogorov complexity [4, 5]. I studied the results of algorithmic complexity heuristic measurements on different and random networks that differ in size-4 motifs number. I found impressive results that show a logarithmic trend line (or maybe power trend line) for the algorithmic complexity with increasing the number of layers. Also, the algorithmic complexity decreases when the number of motifs increases. Thus, there can be a mathematical connection between the algorithmic complexity, the number of motifs, the number of layers, the number of edges and the number of nodes. Furthermore, more research is required to investigate and invent a mathematical expression between these characteristics. Also, more research is needed to assert the correctness of these conclusions on other kinds of networks with different motifs size.
Eftersom problemet med att bestämma komplexiteten hos flerfaldiga nätverk är ett NP-svårt problem, bestämde jag mig för att beräkna komplexiteten hos grafer med hjälp av heuristik. Jag är den första på den här vägen som gjorde den här typen av beräkningar. Jag ville alltid definiera komplexitet som en matematisk egenskap i diagramstrukturen. Denna uppsats undersöker beteendet hos den algoritmiska komplexiteten av flerfaldiga nätverk i grafer för att upptäcka om det är möjligt att extrahera ett matematiskt uttryck som kan representera det. Om vi får en matematisk representation för grafkomplexitet, hanterar vi detta problem från det NP- hårda problemområdet. Den kan också användas som en av diagrammets egenskaper, såsom antalet noder, kanter eller motiv av en viss storlek. Den algoritmiska komplexiteten av flerfaldiga nätverk definieras av Santoro och Nicosia i deras forskningspapper [1]. Således kan ett tillvägagångssätt som använder en heuristisk strategi vara det enklaste sättet att komma nära en optimal matematisk definition av komplexiteten i grafer. I denna avhandling introducerar jag den senaste representationen av den algoritmiska komplexiteten [2] för flerfaldiga nätverk ur ett algoritmiskt perspektiv för informationsteori [3]. Denna definition beror främst på Kolmogorov-komplexiteten [4, 5 ]. Jag studerade resultaten av de heuristiska algoritmiska komplexitetsmätningarna på olika och slumpmässiga nätverk som skiljer sig åt i storlek-4-motivnummer. Jag hittade imponerande resultat som visar en logaritmisk trendlinje (eller kanske krafttrendlinje) för den algoritmiska komplexiteten med att öka antalet lager. Den algoritmiska komplexiteten minskar också när antalet motiv ökar. Således kan det finnas en matematisk koppling mellan den algoritmiska komplexiteten, antalet motiv, antalet lager, antalet kanter och antalet noder. Dessutom krävs mer forskning för att undersöka och uppfinna ett matematiskt uttryck mellan dessa egenskaper. Dessutom behövs mer forskning för att hävda riktigheten av dessa slutsatser på andra olika typer av nätverk.

APA, Harvard, Vancouver, ISO, and other styles

11

Bahramgiri, Moshen. "Algorithmic approaches to graph states under the action of local Clifford groups." Thesis, Massachusetts Institute of Technology, 2007. http://hdl.handle.net/1721.1/38936.

Full text

Abstract:

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007.
Includes bibliographical references (p. 87-88).
Graph states are quantum states (quantum codes) in qn-dimensional space ... (q being a power of some prime number) which can be described by graphs with edges labeled from the field of order q, Fq. Graph states are determined as a common eigenvector of independent elements of the n-fold Pauli group, on which the local Clifford group has a natural action. This action induces the natural action of the local Clifford group on graph states and hence, its action on graphs. Locally equivalent graphs can be described using this action. For q being a prime number, two graphs are locally equivalent when they are located on the same orbit of this action, in other words, when there is an element of the local Clifford group mapping one graph to the other one. When q is some power of a prime number, the definition of this action is the natural generalization of this action in the case where q is prime. We translate the action of local Clifford groups on graphs to a set of linear and quadratic equations in the field F,. In the case that q is an odd number, given two arbitrary graphs, we present an efficient algorithm (polynomial in n) to verify whether these graphs are locally equivalent or not. Moreover, we present a computational method to calculate the number of inequivalent graph states. We give some estimations on the size of the orbits of this action on graphs, and prove that when either q is equal to 2 or is an odd number, the number of inequivalent quantum codes (i.e., the number of classes of equivalency) is equal to ..., which is essentially as large as the total number of graphs.
by Mohsen Bahramgiri.
Ph.D.

APA, Harvard, Vancouver, ISO, and other styles

12

Limnios, Stratis. "Graph Degeneracy Studies for Advanced Learning Methods on Graphs and Theoretical Results Edge degeneracy: Algorithmic and structural results Degeneracy Hierarchy Generator and Efficient Connectivity Degeneracy Algorithm A Degeneracy Framework for Graph Similarity Hcore-Init: Neural Network Initialization based on Graph Degeneracy." Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX038.

Full text

Abstract:

L'extraction de sous-structures significatives a toujours été un élément clé de l’étude des graphes. Dans le cadre de l'apprentissage automatique, supervisé ou non, ainsi que dans l'analyse théorique des graphes, trouver des décompositions spécifiques et des sous-graphes denses est primordial dans de nombreuses applications comme entre autres la biologie ou les réseaux sociaux.Dans cette thèse, nous cherchons à étudier la dégénérescence de graphe, en partant d'un point de vue théorique, et en nous appuyant sur nos résultats pour trouver les décompositions les plus adaptées aux tâches à accomplir. C'est pourquoi, dans la première partie de la thèse, nous travaillons sur des résultats structurels des graphes à arête-admissibilité bornée, prouvant que de tels graphes peuvent être reconstruits en agrégeant des graphes à degré d’arête quasi-borné. Nous fournissons également des garanties de complexité de calcul pour les différentes décompositions de la dégénérescence, c'est-à-dire si elles sont NP-complètes ou polynomiales, selon la longueur des chemins sur lesquels la dégénérescence donnée est définie.Dans la deuxième partie, nous unifions les cadres de dégénérescence et d'admissibilité en fonction du degré et de la connectivité. Dans ces cadres, nous choisissons les plus expressifs, d'une part, et les plus efficaces en termes de calcul d'autre part, à savoir la dégénérescence 1-arête-connectivité pour expérimenter des tâches de dégénérescence standard, telle que la recherche d’influenceurs.Suite aux résultats précédents qui se sont avérés peu performants, nous revenons à l'utilisation du k-core mais en l’intégrant dans un cadre supervisé, i.e. les noyaux de graphes. Ainsi, en fournissant un cadre général appelé core-kernel, nous utilisons la décomposition k-core comme étape de prétraitement pour le noyau et appliquons ce dernier sur chaque sous-graphe obtenu par la décomposition pour comparaison. Nous sommes en mesure d'obtenir des performances à l’état de l’art sur la classification des graphes au prix d’une légère augmentation du coût de calcul.Enfin, nous concevons un nouveau cadre de dégénérescence de degré s’appliquant simultanément pour les hypergraphes et les graphes biparties, dans la mesure où ces derniers sont les graphes d’incidence des hypergraphes. Cette décomposition est ensuite appliquée directement à des architectures de réseaux de neurones pré-entrainés étant donné qu'elles induisent des graphes biparties et utilisent le core d'appartenance des neurones pour réinitialiser les poids du réseaux. Cette méthode est non seulement plus performant que les techniques d'initialisation de l’état de l’art, mais il est également applicable à toute paire de couches de convolution et linéaires, et donc adaptable à tout type d'architecture
Extracting Meaningful substructures from graphs has always been a key part in graph studies. In machine learning frameworks, supervised or unsupervised, as well as in theoretical graph analysis, finding dense subgraphs and specific decompositions is primordial in many social and biological applications among many others.In this thesis we aim at studying graph degeneracy, starting from a theoretical point of view, and building upon our results to find the most suited decompositions for the tasks at hand.Hence the first part of the thesis we work on structural results in graphs with bounded edge admissibility, proving that such graphs can be reconstructed by aggregating graphs with almost-bounded-edge-degree. We also provide computational complexity guarantees for the different degeneracy decompositions, i.e. if they are NP-complete or polynomial, depending on the length of the paths on which the given degeneracy is defined.In the second part we unify the degeneracy and admissibility frameworks based on degree and connectivity. Within those frameworks we pick the most expressive, on the one hand, and computationally efficient on the other hand, namely the 1-edge-connectivity degeneracy, to experiment on standard degeneracy tasks, such as finding influential spreaders.Following the previous results that proved to perform poorly we go back to using the k-core but plugging it in a supervised framework, i.e. graph kernels. Thus providing a general framework named core-kernel, we use the k-core decomposition as a preprocessing step for the kernel and apply the latter on every subgraph obtained by the decomposition for comparison. We are able to achieve state-of-the-art performance on graph classification for a small computational cost trade-off.Finally we design a novel degree degeneracy framework for hypergraphs and simultaneously on bipartite graphs as they are hypergraphs incidence graph. This decomposition is then applied directly to pretrained neural network architectures as they induce bipartite graphs and use the coreness of the neurons to re-initialize the neural network weights. This framework not only outperforms state-of-the-art initialization techniques but is also applicable to any pair of layers convolutional and linear thus being applicable however needed to any type of architecture

APA, Harvard, Vancouver, ISO, and other styles

13

Gkantsidis, Christos. "Algorithmic performance of large-scale distributed networks a spectral method approach /." Available online, Georgia Institute of Technology, 2006, 2006. http://etd.gatech.edu/theses/available/etd-12062005-141254/.

Full text

Abstract:

Thesis (Ph. D.)--Computing, Georgia Institute of Technology, 2006.
Mihail, Milena, Committee Chair ; Ammar, Mostafa, Committee Member ; Dovrolis, Constantinos, Committee Member ; Faloutsos, Michalis, Committee Member ; Zegura, Ellen, Committee Member.

APA, Harvard, Vancouver, ISO, and other styles

14

Shukla, Manu. "Algorithmic Distribution of Applied Learning on Big Data." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/100603.

Full text

Abstract:

Machine Learning and Graph techniques are complex and challenging to distribute. Generally, they are distributed by modeling the problem in a similar way as single node sequential techniques except applied on smaller chunks of data and compute and the results combined. These techniques focus on stitching the results from smaller chunks as the best possible way to have the outcome as close to the sequential results on entire data as possible. This approach is not feasible in numerous kernel, matrix, optimization, graph, and other techniques where the algorithm needs access to all the data during execution. In this work, we propose key-value pair based distribution techniques that are widely applicable to statistical machine learning techniques along with matrix, graph, and time series based algorithms. The crucial difference with previously proposed techniques is that all operations are modeled on key-value pair based fine or coarse-grained steps. This allows flexibility in distribution with no compounding error in each step. The distribution is applicable not only in robust disk-based frameworks but also in in-memory based systems without significant changes. Key-value pair based techniques also provide the ability to generate the same result as sequential techniques with no edge or overlap effects in structures such as graphs or matrices to resolve. This thesis focuses on key-value pair based distribution of applied machine learning techniques on a variety of problems. For the first method key-value pair distribution is used for storytelling at scale. Storytelling connects entities (people, organizations) using their observed relationships to establish meaningful storylines. When performed sequentially these computations become a bottleneck because the massive number of entities make space and time complexity untenable. We present DISCRN, or DIstributed Spatio-temporal ConceptseaRch based StorytelliNg, a distributed framework for performing spatio-temporal storytelling. The framework extracts entities from microblogs and event data, and links these entities using a novel ConceptSearch to derive storylines in a distributed fashion utilizing key-value pair paradigm. Performing these operations at scale allows deeper and broader analysis of storylines. The novel parallelization techniques speed up the generation and filtering of storylines on massive datasets. Experiments with microblog posts such as Twitter data and GDELT(Global Database of Events, Language and Tone) events show the efficiency of the techniques in DISCRN. The second work determines brand perception directly from people's comments in social media. Current techniques for determining brand perception, such as surveys of handpicked users by mail, in person, phone or online, are time consuming and increasingly inadequate. The proposed DERIV system distills storylines from open data representing direct consumer voice into a brand perception. The framework summarizes the perception of a brand in comparison to peer brands with in-memory key-value pair based distributed algorithms utilizing supervised machine learning techniques. Experiments performed with open data and models built with storylines of known peer brands show the technique as highly scalable and accurate in capturing brand perception from vast amounts of social data compared to sentiment analysis. The third work performs event categorization and prospect identification in social media. The problem is challenging due to endless amount of information generated daily. In our work, we present DISTL, an event processing and prospect identifying platform. It accepts as input a set of storylines (a sequence of entities and their relationships) and processes them as follows: (1) uses different algorithms (LDA, SVM, information gain, rule sets) to identify themes from storylines; (2) identifies top locations and times in storylines and combines with themes to generate events that are meaningful in a specific scenario for categorizing storylines; and (3) extracts top prospects as people and organizations from data elements contained in storylines. The output comprises sets of events in different categories and storylines under them along with top prospects identified. DISTL utilizes in-memory key-value pair based distributed processing that scales to high data volumes and categorizes generated storylines in near real-time. The fourth work builds flight paths of drones in a distributed manner to survey a large area taking images to determine growth of vegetation over power lines allowing for adjustment to terrain and number of drones and their capabilities. Drones are increasingly being used to perform risky and labor intensive aerial tasks cheaply and safely. To ensure operating costs are low and flights autonomous, their flight plans must be pre-built. In existing techniques drone flight paths are not automatically pre-calculated based on drone capabilities and terrain information. We present details of an automated flight plan builder DIMPL that pre-builds flight plans for drones tasked with surveying a large area to take photographs of electric poles to identify ones with hazardous vegetation overgrowth. DIMPL employs a distributed in-memory key-value pair based paradigm to process subregions in parallel and build flight paths in a highly efficient manner. The fifth work highlights scaling graph operations, particularly pruning and joins. Linking topics to specific experts in technical documents and finding connections between experts are crucial for detecting the evolution of emerging topics and the relationships between their influencers in state-of-the-art research. Current techniques that make such connections are limited to similarity measures. Methods based on weights such as TF-IDF and frequency to identify important topics and self joins between topics and experts are generally utilized to identify connections between experts. However, such approaches are inadequate for identifying emerging keywords and experts since the most useful terms in technical documents tend to be infrequent and concentrated in just a few documents. This makes connecting experts through joins on large dense graphs challenging. We present DIGDUG, a framework that identifies emerging topics by applying graph operations to technical terms. The framework identifies connections between authors of patents and journal papers by performing joins on connected topics and topics associated with the authors at scale. The problem of scaling the graph operations for topics and experts is solved through dense graph pruning and graph joins categorized under their own scalable separable dense graph class based on key-value pair distribution. Comparing our graph join and pruning technique against multiple graph and join methods in MapReduce revealed a significant improvement in performance using our approach.
Doctor of Philosophy
Distribution of Machine Learning and Graph algorithms is commonly performed by modeling the core algorithm in the same way as the sequential technique except implemented on distributed framework. This approach is satisfactory in very few cases, such as depth-first search and subgraph enumerations in graphs, k nearest neighbors, and few additional common methods. These techniques focus on stitching the results from smaller data or compute chunks as the best possible way to have the outcome as close to the sequential results on entire data as possible. This approach is not feasible in numerous kernel, matrix, optimization, graph, and other techniques where the algorithm needs to perform exhaustive computations on all the data during execution. In this work, we propose key-value pair based distribution techniques that are exhaustive and widely applicable to statistical machine learning algorithms along with matrix, graph, and time series based operations. The crucial difference with previously proposed techniques is that all operations are modeled as key-value pair based fine or coarse-grained steps. This allows flexibility in distribution with no compounding error in each step. The distribution is applicable not only in robust disk-based frameworks but also in in-memory based systems without significant changes. Key-value pair based techniques also provide the ability to generate the same result as sequential techniques with no edge or overlap effects in structures such as graphs or matrices to resolve.

APA, Harvard, Vancouver, ISO, and other styles

15

Baste, Julien. "Treewidth : algorithmic, combinatorial, and practical aspects." Thesis, Montpellier, 2017. http://www.theses.fr/2017MONTS065.

Full text

Abstract:

Dans cette thèse, nous étudions la complexité paramétrée de problèmes combinatoires dans les graphes. Plus précisément, nous présentons une multitude d’algorithmes de programmation dynamique ainsi que des réductions montrant que certains de ces algorithmes sont optimaux. Nous nous intéressons principalement à la treewidth, un paramètre de graphes pouvant être vu comme une mesure de distance entre la structure d’un graphe et la structure topologique d’un arbre. Certains de nos algorithmes sont aussi paramétrés par la taille de la solution demandée et le degré maximum du graphe donné en entrée. Nous avons obtenu un certain nombre de résultats dont certains d’entre eux sont listés ci-dessous. Nous présentons un encadrement du nombre de graphes étiquetés de treewidth bornée. Nous étendons le domaine d’application de la théorie de la bidimensionalité par contraction au delà des graphes ne contenant pas de graphe apex en tant que mineur. Nous montrons aussi que la technique des structures de Catalan, outil améliorant l’efficacité des algorithmes résolvant des problèmes de connexité lorsque le graphe d’entrée est creux, ne peut être appliquée à la totalité des problèmes de connectivité, même si l’on ne considère, parmi les graphes creux, que les graphes planaires. Nous considérons le problème F-M-Deletion qui, étant donné une collection de graphes F, un graphe G et un entier k, demande s’il est possible de retirer au plus k sommets de G de telle sorte que le graphe restant ne contienne aucun graphe de F en tant que mineur. Nous considérons aussi la version topologique de ce problème, à savoir F-TM-Deletion. Ces deux problèmes généralisent des problèmes de modification de graphes bien connus tels que Vertex Cover, Feedback Vertex Set et Vertex Planarization. En fonction de la collection de graphes F, nous utilisons différentes techniques de programmation dynamique pour résoudre F-M-Deletion et F-TM-Deletion paramétrés par la treewidth. Nous utilisons des techniques standards, la structure des graphes frontières et l’approche basée sur le rang. En dernier lieu, nous appliquons ces techniques algorithmiques à deux problèmes issus du réseau de communications, à savoir une variation du problème classique de domination et un problème consistant à trouver un arbre couvrant possédant certaines propriétés, et un problème issu de la bioinformatique consistant à construire un arbre contenant en tant que mineur (topologique) un ensemble d’arbres donnés correspondant à des relations d’évolution entre ensembles d’espèces
In this thesis, we study the Parameterized Complexity of combinatorial problems on graphs. More precisely, we present a multitude of dynamic programming algorithms together with reductions showing optimality for some of them. We mostly deal with the graph parameter of treewidth, which can be seen as a measure of how close a graph is to the topological structure of a tree. We also parameterize some of our algorithms by two other parameters, namely the size of a requested solution and the maximum degree of the input graph. We obtain a number of results, some of which are listed in the following. We estimate the number of labeled graphs of bounded treewidth. We extend the horizon of applicability of the theory of contraction Bidimensionality further than apex-minor free graphs, leading to a wider applicability of the design of subexponential dynamic programming algorithms. We show that the Catalan structure technique, that is a tool used to improve algorithm efficiency for connectivity problems where the input graph is restricted to be sparse, cannot be applied to all planar connectivity problems. We consider the F-M-Deletion problem that, given a set of graphs F, a graph G, and an integer k, asks if we can remove at most k vertices from G such that the remaining graph does not contain any graph of F as a minor. We also consider the topological version of this problem, namely F-TM-Deletion. Both problems generalize some well-known vertex deletion problems, namely Vertex Cover, Feedback Vertex Set, and Vertex Planarization. Depending on the set F, we use distinct dynamic programming techniques to solve F-M-Deletion and F-TM-Deletion when parameterized by treewidth. Namely, we use standard techniques, the rank based approach, and the framework of boundaried graphs. Finally, we apply these techniques to two problems originating from Networks, namely a variation of the classical dominating set problem and a problem that consists in finding a spanning tree with specific properties, and to a problem from Bioinformatics, namely that of construcing a tree that contains as a minor (or topological minor) a set of given trees corresponding to the evolutionary relationships between sets of species

APA, Harvard, Vancouver, ISO, and other styles

16

Raymond, Jean-Florent. "Structural and algorithmic aspects of partial orderings of graphs." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT289.

Full text

Abstract:

Le thème central à cette thèse est l'étude des propriétés des classes de graphes définies par sous-structures interdites et leurs applications.La première direction que nous suivons a trait aux beaux ordres. À l'aide de théorèmes de décomposition dans les classes de graphes interdisant une sous-structure, nous identifions celles qui sont bellement-ordonnées. Les ordres et sous-structures considérés sont ceux associés aux notions de contraction et mineur induit. Ensuite, toujours en considérant des classes de graphes définies par sous-structures interdites, nous obtenons des bornes sur des invariants comme le degré, la largeur arborescente, la tree-cut width et un nouvel invariant généralisant la maille.La troisième direction est l'étude des relations entre les invariants combinatoires liés aux problèmes de packing et de couverture de graphes. Dans cette direction, nous établissons de nouvelles relations entre ces invariants pour certaines classes de graphes. Nous présentons également des applications algorithmiques de ces résultats
The central theme of this thesis is the study of the properties of the classes of graphs defined by forbidden substructures and their applications.The first direction that we follow concerns well-quasi-orders. Using decomposition theorems on graph classes forbidding one substructure, we identify those that are well-quasi-ordered. The orders and substructures that we consider are those related to the notions of contraction and induced minor.Then, still considering classes of graphs defined by forbidden substructures, we obtain bounds on invariants such as degree, treewidth, tree-cut width, and a new invariant generalizing the girth.The third direction is the study of the links between the combinatorial invariants related to problems of packing and covering of graphs. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results

APA, Harvard, Vancouver, ISO, and other styles

17

Gkantsidis, Christos. "Algorithmic performance of large-scale distributed networks: A spectral method approach." Diss., Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/10420.

Full text

Abstract:

Complex networks like the Internet, peer-to-peer systems, and emerging sensor and ad-hoc networks are large distributed decentralized communication systems arising repeatedly in today's technology. In such networks it is critical to characterize network performance as the size of the network scales. The focus of my work is to relate basic network performance metrics to structural characteristics of underlying network topologies, and to develop protocols that reinforce and exploit desired structural characteristics. For the case of the Internet at the Autonomous System level, we relate the graph theoretic notions of conductance and spectrum to network clustering and network congestion. In particular, we show how spectral analysis can identify clusters, and how the presence of clusters affects congestion. This is important for network prediction and network simulation. For the case of peer-to-peer networks we relate conductance and spectral gap to the fundamental questions of searching and topology maintenance. We propose new protocols for maintaining peer-to-peer networks with good conductance and low network overhead. We compare the performance of the traditional method of search by flooding to searching by random walks. We isolate cases of practical interest, such as clustered and dynamic network topologies, where the latter have superior performance. The improvement in the performance can be directly quantified in terms of the conductance of the underlying topology. We introduce further hybrid search schemes, of which flooding and random walks are special instances, which aim to improve the performance of searching by using locally maintained information about the network topology.

APA, Harvard, Vancouver, ISO, and other styles

18

Raymond, Jean-Florent. "Structural and algorithmic aspects of partial orderings of graphs." Doctoral thesis, Montpellier, 2016. https://depotuw.ceon.pl/handle/item/1814.

Full text

Abstract:

This thesis falls within the field of Graph Theory. A central theme is the study of exclusion theorems and their uses in related topics. One of them is well-quasi-ordering: we identify well-quasi-ordered subclasses for several orderings of graphs using structural decompositions. A second one the the study of the relations between combinatorial invariants related to problems of packing and covering of combinatorial structures. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results.
Tematyka rozprawy należy do teorii grafów. Głównym tematem rozprawy są twierdzenia opisujące grafy z zabronioną podstrukturą i ich zastosowania. Rozważamy zastosowania takich twierdzeń do teorii dobrego uporządkowania. W szczególności, korzystając z twierdzeń strukturalnych, wskazujemy kilka dobrze uporządkowanych podklas ze względu na różne porządki. Zajmujemy się rownież badaniem relacji pomiędzy niezmiennikami w kontekście problemów pokrywania i pakowania różnych struktur kombinatorycznych. W rozprawie opisujemy rownież algorytmiczne konsekwencje naszych wyników.

APA, Harvard, Vancouver, ISO, and other styles

19

Neuen, Daniel [Verfasser], Martin [Akademischer Betreuer] Grohe, Pascal [Akademischer Betreuer] Schweitzer, and László [Akademischer Betreuer] Babai. "The power of algorithmic approaches to the graph isomorphism problem / Daniel Neuen ; Martin Grohe, Pascal Schweitzer, László Babai." Aachen : Universitätsbibliothek der RWTH Aachen, 2019. http://d-nb.info/1216040826/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Campbell, Newton Henry Jr. "Algorithmic Foundations of Heuristic Search using Higher-Order Polygon Inequalities." NSUWorks, 2016. http://nsuworks.nova.edu/gscis_etd/374.

Full text

Abstract:

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark paradigm. The new heuristic’s novel feature is that it computes and stores a reduced amount of preprocessed information (in comparison to previous landmark-based algorithms) while enabling more informed search decisions. We demonstrate that domination of this heuristic over its predecessor depends on landmark selection and that, in general, the denser the landmark set, the better heuristic performs. Due to the reduced memory requirement, this new heuristic admits much denser landmark sets. We conduct experiments to characterize the impact that landmark configurations have on this new heuristic, demonstrating that centrality-based landmark selection has the best tradeoff between preprocessing and runtime. Using a developed graph library and static information from benchmark road map datasets, the algorithm is compared experimentally with previous landmark-based shortest path techniques in a fixed-memory environment to demonstrate a reduction in overall computational time and memory requirements. Experimental results are evaluated to detail the significance of landmark selection and density, the tradeoffs of performing preprocessing, and the practical use cases of the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

21

Diaz, Boada Juan Sebastian. "Polypharmacy Side Effect Prediction with Graph Convolutional Neural Network based on Heterogeneous Structural and Biological Data." Thesis, KTH, Numerisk analys, NA, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-288537.

Full text

Abstract:

The prediction of polypharmacy side effects is crucial to reduce the mortality and morbidity of patients suffering from complex diseases. However, its experimental prediction is unfeasible due to the many possible drug combinations, leaving in silico tools as the most promising way of addressing this problem. This thesis improves the performance and robustness of a state-of-the-art graph convolutional network designed to predict polypharmacy side effects, by feeding it with complexity properties of the drug-protein network. The modifications also involve the creation of a direct pipeline to reproduce the results and test it with different datasets.
För att minska dödligheten och sjukligheten hos patienter som lider av komplexa sjukdomar är det avgörande att kunna förutsäga biverkningar från polyfarmaci. Att experimentellt förutsäga biverkningarna är dock ogenomförbart på grund av det stora antalet möjliga läkemedelskombinationer, vilket lämnar in silico-verktyg som det mest lovande sättet att lösa detta problem. Detta arbete förbättrar prestandan och robustheten av ett av det senaste grafiska faltningsnätverken som är utformat för att förutsäga biverkningar från polyfarmaci, genom att mata det med läkemedel-protein-nätverkets komplexitetsegenskaper. Ändringarna involverar också skapandet av en direkt pipeline för att återge resultaten och testa den med olika dataset.

APA, Harvard, Vancouver, ISO, and other styles

22

Dusart, Jérémie. "Graph searches with applications to cocomparability graphs." Paris 7, 2014. http://www.theses.fr/2014PA077048.

Full text

Abstract:

Un parcours de graphe est un mécanisme pour visiter de manière itérative les sommets d'un graphe. Cela a été une technique fondamentale dans la conception des algorithmes de graphe depuis les débuts de l'informatique. Bon nombre des premiers parcours étaient basées sur le parcours en largeur(BFS) ou en profondeur (DFS) et cela a donné des algorithmes efficaces pour les problèmes pratiques tels que la distance entre deux sommets, le diamètre, la connectivité, les problèmes de flot et la reconnaissance des graphes planaires. Le but de cette thèse est d'étudier les parcours de graphe Dans cette thèse, nous présentons des résultats généraux sur les parcours de graphe dans les graphes de cocomparabilité, mais aussi une nouvelle caractérisation des graphes de cocomparabilité et des applications des parcours de graphe pour résoudre le problème d'orientation transitive, de sous-graphe triangulé maximal, de clique séparatrice et de sommets simpliciaux. Un modèle simple et général est aussi présenté pour capturer la plupart des parcours de graphe
A graph search is a mechanism for systematically visiting the vertices of a graph. It has been a fundamental technique in the design of graph algorithms since the eraarly days of computer science. Many of the early search methods were based on Breadth First Search (BFS) or Depth First Search (DFS) and resulted in efficient algorithms for practical problems such as the distance between two vertices, diameter, connectivity, network flows and the recognition of planar graphs. The purpose of this thesis is to studied the graph search. In this thesis, we present general result about graph search in cocomparability grapj, but also a new charactrization of cocomparability graph and apllications of graph search to solve the problem of transitive orientation, maximal chordal subgraph, clique perator and simplicial vertices. A simple and general framework is also presented to capture most of the well known graph search

APA, Harvard, Vancouver, ISO, and other styles

23

Legay, Sylvain. "Quelques problèmes d'algorithmique et combinatoires en théorie des grapphes." Thesis, Université Paris-Saclay (ComUE), 2017. http://www.theses.fr/2017SACLS030/document.

Full text

Abstract:

Le sujet de cette thèse est la théorie des graphes. Formellement, un graphe est un ensemble de sommets et un ensemble d’arêtes, c’est à dire de paires de sommets, qui relient les sommets. Cette thèse traite de différents problèmes de décisions binaires ou de minimisations liés à la notion de graphe, et cherche, pour chacun de ces problèmes, à déterminer sa classe de complexité, ou à fournir un algorithme. Le premier chapitre concerne le problème de trouver le plus petit sous-graphe connexe tropical dans un graphe sommet-colorié, c’est à dire le plus petit sous-graphe connexe contenant toutes les couleurs. Le deuxième chapitre concerne les problèmes d’homomorphisme tropical, une généralisation des problèmes de coloriage de graphe. On y trouve un lien entre ces problèmes et plusieurs classes de problèmes d’homomorphismes, dont la classe des Problèmes de Satisfaction de Contraintes. Le troisième chapitre concerne deux variantes lointaines du problème de domination, nommément les problèmes d’alliances globales dans un graphe pondéré et le problème de l’ensemble sûr. Le quatrième chapitre concerne la recherche d’une décomposition arborescente étoilée, c’est à dire une décomposition arborescente dont le rayon des sacs est 1. Enfin, le cinquième chapitre concerne une variante du problème de décider du comportement asymptotique de l’itéré du graphe des bicliques
This thesis is about graph theory. Formally, a graph is a set of vertices and a set of edges, which are pair of vertices, linking vertices. This thesis deals with various decision problem linked to the notion of graph, and, for each of these problem, try to find its complexity class, or to give an algorithm. The first chapter is about the problem of finding the smallest connected tropical subgraph of a vertex-colored graph, which is the smallest connecter subgraph containing every colors. The second chapter is about problems of tropical homomorphism, a generalization of coloring problem. A link between these problems and several other class of homomorphism problems can be found in this chapter, especially with the class of Constraint Satisfaction Problem. The third chapter is about two variant of the domination problem, namely the global alliance problems in a weighted graph and the safe set problem. The fourth chapter is about the problem of finding a star tree-decomposition, which is a tree-decomposition where the radius of bags is 1. Finally, the fifth chapter is about a variant of the problem of deciding the asymptotic behavior of the iterated biclique graph

APA, Harvard, Vancouver, ISO, and other styles

24

Larsson, Patrik. "Analyzing and adapting graph algorithms for large persistent graphs." Thesis, Linköping University, Department of Computer and Information Science, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-15422.

Full text

Abstract:

In this work, the graph database Neo4j developed by Neo Technology is presented together with some of it's functionality when it comes to accessing data as a graph. This type of data access brings the possibility to implement common graph algorithms on top of Neo4j. Examples of such algorithms are presented together with their theoretical backgrounds. These are mainly algorithms for finding shortest paths and algorithms for different graph measures such as centrality measures. The implementations that have been made are presented, as well as complexity analysis and the performance measures performed on them. The conclusions include that Neo4j is well suited for these types of implementations.

APA, Harvard, Vancouver, ISO, and other styles

25

Zhou, Hang. "Graph algorithms : network inference and planar graph optimization." Thesis, Paris, Ecole normale supérieure, 2015. http://www.theses.fr/2015ENSU0016/document.

Full text

Abstract:

Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques
This thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently

APA, Harvard, Vancouver, ISO, and other styles

26

Duhaze-Pradines, Loric. "Reachability problems for general rotor walks in graphs." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG051.

Full text

Abstract:

Nous nous intéressons dans cette thèse aux propriétés algorithmiques d'un automate cellulaire, les marches de rotors. Ce modèle a été introduit de deux manières différentes. Tout d'abord comme une opération élémentaire d'un autre automate cellulaire : les Sandpiles qui modélisent l'effondrement d'une pile de sable lorsque celle-ci devient trop haute. Mais également, par sa ressemblance avec des modèles stochastiques très étudiés que sont les marches aléatoires. En effet, de nombreuses propriétés structurelles des marches aléatoires (temps d'atteinte, temps de couverture, etc...) sont similaires à celles de cet automate complètement déterministe qu'est la marche de rotor. Cette forme de "dérandomisation" de processus aléatoire a été la motivation principale de cette thèse. Plus précisément, une marche de rotor correspond au mouvement d'une particule sur un graphe orienté en suivant la règle suivante : au départ on fixe un ordre (une numérotation) sur les arcs sortants de chacun des sommets du graphe puis, une fois qu'on a définit la position de départ de la particule, chaque fois que cette dernière est sur un sommet, elle le quitte par l'arc de valeur la plus faible qu'elle n'a pas déjà utilisé. Bien entendu, si tous les arcs ont été utilisés, on redémarre avec l'arc de plus faible valeur. Il existe une multitude de problèmes d'accessibilité sur les rotors dont nous nous appliquons à faire une liste dans cette thèse. Nous donnerons également des résultats de complexité pour certains d'entre eux. Puis nous nous intéresserons à un problème d'accessibilité particulier : ARRIVAL. Si l'on considère un graphe avec des puits tel qu'il existe un chemin orienté entre chaque sommet du graphe et au moins l'un de ces puits, une marche de rotor se termine forcément. Hélas, le nombre d'étapes avant que ce processus ne termine peut être exponentiel. En 2017, Dorhau et al. ont présenté un problème, nommé ARRIVAL, qui est de savoir si la particule finit bien sa course dans un puits donné. Ils ont montré qu'il appartenait aux classes de complexité NP et co-NP. Etant donc un bon candidat à être résolu par un algorithme polynomial, nous nous intéressons à ce problème sur une sous-classe de graphe pour laquelle le nombre d'étapes du processus peut être exponentiel : les Tree-like multigraphes. Il s'agit de multigraphes donc le graphe non-orienté sous-jacent est un arbre. Dans ce contexte, nous avons pu montrer que ce problème pouvait être résolu en temps linéaire et même étendre ces résultats à des versions décisionnelles du problème ARRIVAL connues pour être respectivement NP-complète et PSPACE-complète
In this thesis, we focus on the algorithmic properties of a cellular automaton known as rotor walks. This model has been introduced in two distinct ways. Firstly, as a fundamental operation within another cellular automaton known as Sandpiles, which models the collapse of a sand pile when it becomes too high. Secondly, due to its resemblance to well-studied stochastic models, such as random walks. Indeed, numerous structural properties of random walks (hitting times, cover times, etc.) are analogous to those of this completely deterministic automaton called the rotor walk. The main motivation for this thesis stems from this "derandomization" of a random process. More precisely, a rotor walk corresponds to the movement of a particle on a directed graph following the following rule: initially, an order (a numbering) is fixed on the outgoing arcs of each vertex of the graph. Once the starting position of the particle is defined, each time it is on a vertex, it leaves through the arc with the lowest value that it has not already used. Of course, if all arcs have been used, the process restarts with the lowest value arc. There is a multitude of accessibility problems on rotors, and we aim to compile a list of them in this thesis. We also provide complexity results for some of these problems. Subsequently, we turn our attention to a specific accessibility problem: ARRIVAL. Considering a graph with sinks such that there is a directed path between each vertex of the graph and at least one of these sinks, a rotor walk inevitably terminates. Unfortunately, the number of steps before this process concludes can be exponential. In 2017, Dorhau et al. introduced a problem called ARRIVAL, which seeks to determine if the particle successfully reaches a given sink. They demonstrated that it belongs to the complexity classes NP and co-NP. Being a strong candidate for polynomial algorithm resolution, we investigate this problem on a subclass of graphs where the step count of the process can be exponential: Tree-like multigraphs. These are multigraphs whose underlying undirected graph is a tree. In this context, we show that this problem can be solved in linear time, extending these results to decision versions of the ARRIVAL problem, known to be respectively NP-complete and PSPACE-complete

APA, Harvard, Vancouver, ISO, and other styles

27

Mądry, Aleksander. "From graphs to matrices, and back : new techniques for graph algorithms." Thesis, Massachusetts Institute of Technology, 2011. http://hdl.handle.net/1721.1/66014.

Full text

Abstract:

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 181-192).
The growing need to deal efficiently with massive computing tasks prompts us to consider the following question: How well can we solve fundamental optimization problems if our algorithms have to run really quickly? The motivation for the research presented in this thesis stems from addressing the above question in the context of algorithmic graph theory. To pursue this direction, we develop a toolkit that combines a diverse set of modern algorithmic techniques, including sparsification, low-stretch spanning trees, the multiplicative-weights-update method, dynamic graph algorithms, fast Laplacian system solvers, and tools of spectral graph theory. Using this toolkit, we obtain improved algorithms for several basic graph problems including: -- The Maximum s-t Flow and Minimum s-t Cut Problems. We develop a new approach to computing (1 - [epsilon])-approximately maximum s-t flow and (1 + [epsilon])-approximately minimum s-t cut in undirected graphs that gives the fastest known algorithms for these tasks. These algorithms are the first ones to improve the long-standing bound of O(n3/2') running time on sparse graphs; -- Multicommodity Flow Problems. We set forth a new method of speeding up the existing approximation algorithms for multicommodity flow problems, and use it to obtain the fastest-known (1 - [epsilon])-approximation algorithms for these problems. These results improve upon the best previously known bounds by a factor of roughly [omega](m/n), and make the resulting running times essentially match the [omega](mn) "flow-decomposition barrier" that is a natural obstacle to all the existing approaches; -- " Undirected (Multi-)Cut-Based Minimization Problems. We develop a general framework for designing fast approximation algorithms for (multi-)cutbased minimization problems in undirected graphs. Applying this framework leads to the first algorithms for several fundamental graph partitioning primitives, such as the (generalized) sparsest cut problem and the balanced separator problem, that run in close to linear time while still providing polylogarithmic approximation guarantees; -- The Asymmetric Traveling Salesman Problem. We design an O( )- approximation algorithm for the classical problem of combinatorial optimization: the asymmetric traveling salesman problem. This is the first asymptotic improvement over the long-standing approximation barrier of e(log n) for this problem; -- Random Spanning Tree Generation. We improve the bound on the time needed to generate an uniform random spanning tree of an undirected graph.
by Aleksander Mądry.
Ph.D.

APA, Harvard, Vancouver, ISO, and other styles

28

Duffy, Christopher. "Homomorphisms of (j, k)-mixed graphs." Thesis, Bordeaux, 2015. http://hdl.handle.net/1828/6601.

Full text

Abstract:

A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs). A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively. In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number. In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of iii a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs. In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs. In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.
Graduate

APA, Harvard, Vancouver, ISO, and other styles

29

Dodo, Meva. "Etude de l'apport de la visualisation 3D interactive pour l'administration de systèmes complexe." Toulouse 3, 2008. http://thesesups.ups-tlse.fr/358/.

Full text

Abstract:

Cette thèse propose de nouvelles méthodes qui permettent de faciliter l'analyse et la compréhension de la structure des systèmes complexes ainsi que les différents événements générés par les ressources. Des techniques de représentation 3D sont proposées afin de permettre la visualisation de tout type de structure de systèmes complexes. Notre approche est matérialisée par un nouvel algorithme d'affichage 3D de larges graphes. Cette algorithme est basé sur une nouvelle approche d'optimisation de l'algorithme force-attraction-répulsion (FDP) afin mieux de distribuer les nœuds d'un graphe dans un espace 3D, et nous l'avons associé à des méthodes d'optimisation afin d'améliorer sa performance. La deuxième approche se propose d'associer à la représentation 3D du graphe des mondes 3D qui facilitent l'analyse et l'exploration de la structure du système à étudier
The aim of this thesis is to study new methods which allow to improve the understanding of complex systems' structure and to analyze the various events generated by its resources. Three-dimensional techniques are proposed to easy the analysis of the structure of complex systems. A new algorithm for drawing, in 3D, large graphs is proposed in order to optimize the layout of a complex structure. Our method is based on the optimization of the force-directed placement algorithm (FDP) that allows effectively and aesthetically displaying large graphs. Our second approach is to propose metaphors that allow to easily understand the different events generated by devices. This approach is based on the three attributes that define an event: "what, when, where", and it is associated with filtering techniques that choose interesting events according to the management needs

APA, Harvard, Vancouver, ISO, and other styles

30

Slade, Michael L. "A layout algorithm for hierarchical graphs with constraints /." Online version of thesis, 1994. http://hdl.handle.net/1850/11724.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Schiller, Benjamin. "Graph-based Analysis of Dynamic Systems." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-230611.

Full text

Abstract:

The analysis of dynamic systems provides insights into their time-dependent characteristics. This enables us to monitor, evaluate, and improve systems from various areas. They are often represented as graphs that model the system's components and their relations. The analysis of the resulting dynamic graphs yields great insights into the system's underlying structure, its characteristics, as well as properties of single components. The interpretation of these results can help us understand how a system works and how parameters influence its performance. This knowledge supports the design of new systems and the improvement of existing ones. The main issue in this scenario is the performance of analyzing the dynamic graph to obtain relevant properties. While various approaches have been developed to analyze dynamic graphs, it is not always clear which one performs best for the analysis of a specific graph. The runtime also depends on many other factors, including the size and topology of the graph, the frequency of changes, and the data structures used to represent the graph in memory. While the benefits and drawbacks of many data structures are well-known, their runtime is hard to predict when used for the representation of dynamic graphs. Hence, tools are required to benchmark and compare different algorithms for the computation of graph properties and data structures for the representation of dynamic graphs in memory. Based on deeper insights into their performance, new algorithms can be developed and efficient data structures can be selected. In this thesis, we present four contributions to tackle these problems: A benchmarking framework for dynamic graph analysis, novel algorithms for the efficient analysis of dynamic graphs, an approach for the parallelization of dynamic graph analysis, and a novel paradigm to select and adapt graph data structures. In addition, we present three use cases from the areas of social, computer, and biological networks to illustrate the great insights provided by their graph-based analysis. We present a new benchmarking framework for the analysis of dynamic graphs, the Dynamic Network Analyzer (DNA). It provides tools to benchmark and compare different algorithms for the analysis of dynamic graphs as well as the data structures used to represent them in memory. DNA supports the development of new algorithms and the automatic verification of their results. Its visualization component provides different ways to represent dynamic graphs and the results of their analysis. We introduce three new stream-based algorithms for the analysis of dynamic graphs. We evaluate their performance on synthetic as well as real-world dynamic graphs and compare their runtimes to snapshot-based algorithms. Our results show great performance gains for all three algorithms. The new stream-based algorithm StreaM_k, which counts the frequencies of k-vertex motifs, achieves speedups up to 19,043 x for synthetic and 2882 x for real-world datasets. We present a novel approach for the distributed processing of dynamic graphs, called parallel Dynamic Graph Analysis (pDNA). To analyze a dynamic graph, the work is distributed by a partitioner that creates subgraphs and assigns them to workers. They compute the properties of their respective subgraph using standard algorithms. Their results are used by the collator component to merge them to the properties of the original graph. We evaluate the performance of pDNA for the computation of five graph properties on two real-world dynamic graphs with up to 32 workers. Our approach achieves great speedups, especially for the analysis of complex graph measures. We introduce two novel approaches for the selection of efficient graph data structures. The compile-time approach estimates the workload of an analysis after an initial profiling phase and recommends efficient data structures based on benchmarking results. It achieves speedups of up to 5.4 x over baseline data structure configurations for the analysis of real-word dynamic graphs. The run-time approach monitors the workload during analysis and exchanges the graph representation if it finds a configuration that promises to be more efficient for the current workload. Compared to baseline configurations, it achieves speedups up to 7.3 x for the analysis of a synthetic workload. Our contributions provide novel approaches for the efficient analysis of dynamic graphs and tools to further investigate the trade-offs between different factors that influence the performance.

APA, Harvard, Vancouver, ISO, and other styles

32

Pennarun, Claire. "Planar graphs : non-aligned drawings, power domination and enumeration of Eulerian orientations." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0609/document.

Full text

Abstract:

Dans cette thèse, nous présentons trois problèmes concernant les graphes planaires.Nous travaillons tout d'abord sur les dessins planaires non-alignés, c'est-à-dire des dessins planaires de graphes sur une grille sans que deux sommets se trouvent sur la même ligne ou la même colonne.Nous caractérisons les graphes planaires possédant un tel dessin sur une grille de taille $n times n$, et nous présentons deux algorithmes générant un dessin planaire non-aligné avec arêtes brisées sur cette grille pour tout graphe planaire, avec $n-3$ ou $min(frac{2n-3}{5},$ $#{text{triangles s{'e}parateurs}}+1)$ brisures au total.Nous proposons également deux algorithmes dessinant un dessin planaire non-aligné sur des grilles d'aire $O(n^4)$. Nous donnons des résultats spécifiques concernant les graphes 4-connexes et de type triangle-emboîté.Le second sujet de cette thèse est la domination de puissance dans les graphes planaires. Nous exhibons une famille de graphes ayant un nombre de domination de puissance $gamma_P$ au moins égal à $frac{n}{6}$. Nous montrons aussi que pour tout graphe planaire maximal $G$ à $n geq 6$ sommets, $gamma_P(G) leq frac{n-2}{4}$. Enfin, nous étudions les grilles triangulaires $T_k$ à bord hexagonal de dimension $k$ et nous montrons que $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Nous étudions également l'énumération des orientations planaires Eulériennes. Nous proposons une nouvelle décomposition de ces cartes. En considérant les orientations des dernières $2k-1$ arêtes autour de la racine, nous définissons des sous- et sur-ensembles des orientations planaires Eulériennes paramétrés par $k$.Pour chaque classe, nous proposons un système d'équations fonctionnelles définissant leur série génératrice, et nous prouvons que celle-ci est toujours algébrique. Nous montrons ainsi que la constance de croissance des orientations planaires Eulériennes est entre 11.56 et 13.005
In this thesis, we present results on three different problems concerning planar graphs.We first give some new results on planar non-aligned drawings, i.e. planar grid drawings where vertices are all on different rows and columns.We show that not every planar graph has a non-aligned drawing on an $n times n$-grid, but we present two algorithms generating a non-aligned polyline drawings on such a grid requiring either $n-3$ or $min(frac{2n-3}{5},$ $#{text{separating triangles}}+1)$ bends in total.Concerning non-minimal grids, we give two algorithms drawing a planar non-aligned drawing on grids with area of order $n^4$. We also give specific results for 4-connected graphs and nested-triangle graphs.The second topic is power domination in planar graphs. We present a family of graphs with power dominating number $gamma_P$ at least $frac{n}{6}$. We then prove that for every maximal planar graph $G$ of order $n$, $gamma_P(G) leq frac{n-2}{4}$, and we give a constructive algorithm.We also prove that for triangular grids $T_k$ of dimension $k$ with hexagonal-shape border, $frac{k}{3} - frac{1}{6} leq gamma_P(T_k) leq lceil frac{k}{3} rceil$.Finally, we focus on the enumeration of planar Eulerian orientations. After proposing a new decomposition for these maps, we define subsets and supersets of planar Eulerian orientations with parameter $k$, generated by looking at the orientations of the last $2k-1$ edges around the root vertex.For each set, we give a system of functional equations defining its generating function, and we prove that it is always algebraic.This way, we show that the growth rate of planar Eulerian orientations is between 11.56 and 13.005

APA, Harvard, Vancouver, ISO, and other styles

33

Bui, Thang Nguyen. "Graph bisection algorithms." Thesis, Massachusetts Institute of Technology, 1986. http://hdl.handle.net/1721.1/77680.

Full text

Abstract:

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1986.
MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.
Bibliography: leaves 64-66.
by Thang Nguyen Bui.
Ph.D.

APA, Harvard, Vancouver, ISO, and other styles

34

Gillet, Noel. "Optimisation de requêtes sur des données massives dans un environnement distribué." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0553/document.

Full text

Abstract:

Les systèmes de stockage distribués sont massivement utilisés dans le contexte actuel des grandes masses de données. En plus de gérer le stockage de ces données, ces systèmes doivent répondre à une quantité toujours plus importante de requêtes émises par des clients distants afin d’effectuer de la fouille de données ou encore de la visualisation. Une problématique majeure dans ce contexte consiste à répartir efficacement les requêtes entre les différents noeuds qui composent ces systèmes afin de minimiser le temps de traitement des requêtes ( temps maximum et en moyenne d’une requête, temps total de traitement pour toutes les requêtes...). Dans cette thèse nous nous intéressons au problème d’allocation de requêtes dans un environnement distribué. On considère que les données sont répliquées et que les requêtes sont traitées par les noeuds stockant une copie de la donnée concernée. Dans un premier temps, des solutions algorithmiques quasi-optimales sont proposées lorsque les communications entre les différents noeuds du système se font de manière asynchrone. Le cas où certains noeuds du système peuvent être en panne est également considéré. Dans un deuxième temps, nous nous intéressons à l’impact de la réplication des données sur le traitement des requêtes. En particulier, un algorithme qui adapte la réplication des données en fonction de la demande est proposé. Cet algorithme couplé à nos algorithmes d’allocation permet de garantir une répartition des requêtes proche de l’idéal pour toute distribution de requêtes. Enfin, nous nous intéressons à l’impact de la réplication quand les requêtes arrivent en flux sur le système. Nous procédons à une évaluation expérimentale sur la base de données distribuées Apache Cassandra. Les expériences réalisées confirment l’intérêt de la réplication et de nos algorithmes d’allocation vis-à-vis des solutions présentes par défaut dans ce système
Distributed data store are massively used in the actual context of Big Data. In addition to provide data management features, those systems have to deal with an increasing amount of queries sent by distant users in order to process data mining or data visualization operations. One of the main challenge is to evenly distribute the workload of queries between the nodes which compose these system in order to minimize the treatment time. In this thesis, we tackle the problem of query allocation in a distributed environment. We consider that data are replicated and a query can be handle only by a node storing the concerning data. First, near-optimal algorithmic proposals are given when communications between nodes are asynchronous. We also consider that some nodes can be faulty. Second, we study more deeply the impact of data replication on the query treatement. Particularly, we present an algorithm which manage the data replication based on the demand on these data. Combined with our allocation algorithm, we guaranty a near-optimal allocation. Finally, we focus on the impact of data replication when queries are received as a stream by the system. We make an experimental evaluation using the distributed database Apache Cassandra. The experiments confirm the interest of our algorithmic proposals to improve the query treatement compared to the native allocation scheme in Cassandra

APA, Harvard, Vancouver, ISO, and other styles

35

Despré, Vincent. "Topologie et algorithmes sur les cartes combinatoires." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM043/document.

Full text

Abstract:

Dans cette thèse, nous nous intéressons aux propriétés topologiques des surfaces, i.e. celles qui sont préservées par des déformations continues. Intuitivement, ces propriétés peuvent être imaginées comme étant celles qui décrivent le forme générale des surfaces. Nous utilisons des cartes combinatoires pour décrire les surfaces. Elles ont le double avantage d'être de naturels objets mathématiques et de pouvoir être transformées naturellement en structure de données.Nous étudions trois problèmes différents. Premièrement, nous donnons des algorithmes pour calculer le nombre géométrique d'intersection de courbes dessinées sur des surfaces. Nous avons obtenu un algorithm quadratique pour calculer le nombre minimal d'auto-intersections dans une classe d'homotopie, un algorithme quartique pour construire un représentant minimal et un algorithme quasi-linéaire pour décider si une classe d'homotopie contient une courbe simple. Ensuite, nous donnons des contre-exemples à une conjecture de Mohar et Thomassen au sujet de l'existence de cycles de partage dans les triangulations. Finalement, nous utilisons les travaux récents de Lévèque et Gonçalves à propos des bois de Schnyder toriques pour construire une bijection entre les triangulations du tore et certaines cartes unicellulaires analogue à le célèbre bijection de Poulalhon et Schaeffer pour les triangulations planaires.Plusieurs points de vue sont utilisés au cours de cette thèse. Nous proposons donc un important chapitre préliminaire où nous insistons sur les connections entre ces différents points de vue
In this thesis, we focus on the topological properties of surfaces, i.e. those that are preserved by continuous deformations. Intuitively, it can be understood as the properties that describe the general shape of surfaces. We describe surfaces as combinatorial maps. They have the double advantage of being well defined mathematical objects and of being straightforwardly transformed into data-structures.We study three distinct problems. Firstly, we give algorihtms to compute geometric intersection numbers of curves on surfaces. We obtain a quadratic algorithm to compute the minimal number of self-intersections in a homotopy class, a quartic one to construct a minimal representative and a quasi-linear one to decide if a homotopy class contains a simple curve. Secondly, we give counter-examples to a conjecture of Mohar and Thomassen about the existence of splitting cycles in triangulations. Finally, we use the recent work of Gonçalves and Lévèque about toiroidal Schnyder woods to describe a bijection between toroidal triangulations and toroidal unicellular maps analogous to the well known bijection of Poulalhon and Schaeffer for planar triangulations.Many different points of view are involved in this thesis. We thus propose a large preliminary chapter where we provide connections between the different viewpoints

APA, Harvard, Vancouver, ISO, and other styles

36

Nanongkai, Danupon. "Graph and geometric algorithms on distributed networks and databases." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41056.

Full text

Abstract:

In this thesis, we study the power and limit of algorithms on various models, aiming at applications in distributed networks and databases. In distributed networks, graph algorithms are fundamental to many applications. We focus on computing random walks which are an important primitive employed in a wide range of applications but has always been computed naively. We show that a faster solution exists and subsequently develop faster algorithms by exploiting random walk properties leading to two immediate applications. We also show that this algorithm is optimal. Our technique in proving a lower bound show the first non-trivial connection between communication complexity and lower bounds of distributed graph algorithms. We show that this technique has a wide range of applications by proving new lower bounds of many problems. Some of these lower bounds show that the existing algorithms are tight. In database searching, we think of the database as a large set of multi-dimensional points stored in a disk and want to help the users to quickly find the most desired point. In this thesis, we develop an algorithm that is significantly faster than previous algorithms both theoretically and experimentally. The insight is to solve the problem on the streaming model which helps emphasize the benefits of sequential access over random disk access. We also introduced the randomization technique to the area. The results were complemented with a lower bound. We also initiat a new direction as an attempt to get a better query. We are the first to quantify the output quality using "user satisfaction" which is made possible by borrowing the idea of modeling users by utility functions from game theory and justify our approach through a geometric analysis.

APA, Harvard, Vancouver, ISO, and other styles

37

Aji, Sudarshan Mandayam. "Estimating Reachability Set Sizes in Dynamic Graphs." Thesis, Virginia Tech, 2014. http://hdl.handle.net/10919/49262.

Full text

Abstract:

Graphs are a commonly used abstraction for diverse kinds of interactions, e.g., on Twitter and Facebook. Different kinds of topological properties of such graphs are computed for gaining insights into their structure. Computing properties of large real networks is computationally very challenging. Further, most real world networks are dynamic, i.e., they change over time. Therefore there is a need for efficient dynamic algorithms that offer good space-time trade-offs. In this thesis we study the problem of computing the reachability set size of a vertex, which is a fundamental problem, with applications in databases and social networks. We develop the first Giraph based algorithms for different dynamic versions of these problems, which scale to graphs with millions of edges.
Master of Science

APA, Harvard, Vancouver, ISO, and other styles

38

Bury, Marc [Verfasser], Beate [Akademischer Betreuer] Bollig, and Martin [Gutachter] Sauerhoff. "On graph algorithms for large-scale graphs / Marc Bury. Betreuer: Beate Bollig. Gutachter: Martin Sauerhoff." Dortmund : Universitätsbibliothek Dortmund, 2015. http://d-nb.info/1112468595/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Nadal, Maurin. "Assistance à l'utilisateur novice dans le cadre du dessin de graphe à l'aide de méthodes d'apprentissage." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2013. http://tel.archives-ouvertes.fr/tel-00981993.

Full text

Abstract:

Cette thèse se concentre sur la problématique suivante : comment assister un utilisateur novice pour l'aider à obtenir un dessin de son graphe qui soit adapté à ses besoins ? En effet, les méthodes de dessins actuelles, très nombreuses, nécessitent une grande expertise pour obtenir un dessin de bonne qualité. Or, par manque d'expertise, les utilisateurs novices ne peuvent pour l'instant pas produire des dessins d'une telle qualité à partir de leurs données. La solution proposée consiste à mettre en place un système interactif proposant à l'utilisateur différents dessins pour un même graphe afin qu'il obtienne un résultat qui réponde correctement à ses besoins. Ce système se base sur un algorithme de force modifié utilisé par un système d'algorithme génétique hautement modulable. L'objectif de la modification apportée à l'algorithme de dessin étant de pouvoir générer plusieurs dessins intéressants pour un même graphe.

APA, Harvard, Vancouver, ISO, and other styles

40

Prego, Lilach. "Algorithm for directed graph clustering, based on edge weights and the implementation on web graphs /." [S.l.] : [s.n.], 2005. http://lib.haifa.ac.il/theses/general/001344252.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Profiti, Giuseppe <1980&gt. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/1/profiti_giuseppe_tesi.pdf.

Full text

Abstract:

Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, thanks to constraints on the data and dynamic programming. The proposed algorithm ideally improves the generation time by a factor of 5. The graph representation is then exploited to build a comprehensive database, thanks to the rising technology of graph databases. While graph databases are widely used for other kind of data, from Twitter tweets to recommendation systems, their application to bioinformatics is new. A graph database is proposed, with a structure that can be easily expanded and queried.

APA, Harvard, Vancouver, ISO, and other styles

42

Profiti, Giuseppe <1980&gt. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/.

Full text

Abstract:

Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, thanks to constraints on the data and dynamic programming. The proposed algorithm ideally improves the generation time by a factor of 5. The graph representation is then exploited to build a comprehensive database, thanks to the rising technology of graph databases. While graph databases are widely used for other kind of data, from Twitter tweets to recommendation systems, their application to bioinformatics is new. A graph database is proposed, with a structure that can be easily expanded and queried.

APA, Harvard, Vancouver, ISO, and other styles

43

Gajewar, Amita Surendra. "Approximate edge 3-coloring of cubic graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735.

Full text

Abstract:

Thesis (M. S.)--Computing, Georgia Institute of Technology, 2009.
Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.

APA, Harvard, Vancouver, ISO, and other styles

44

Rocha, Mário. "The embedding of complete bipartite graphs onto grids with a minimum grid cutwidth." CSUSB ScholarWorks, 2003. https://scholarworks.lib.csusb.edu/etd-project/2311.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Preissmann, Myriam. "Sur quelques problèmes théoriques et appliqués de la théorie des graphes : [thèse en partie soutenue sur un ensemble de travaux]." Grenoble 1, 1988. http://www.theses.fr/1988GRE10162.

Full text

Abstract:

Etude de la théorie des graphes (graphes cubiques et indice chromatique, graphes parfaits) et applications (problèmes d'optimisation combinatoire associes a des modèles de physique statique, algorithmes heuristiques et exactes pour la simulation rapide d'un VLSI)

APA, Harvard, Vancouver, ISO, and other styles

46

Lancin, Aurélien. "Étude de réseaux complexes et de leurs propriétés pour l’optimisation de modèles de routage." Thesis, Nice, 2014. http://www.theses.fr/2014NICE4117/document.

Full text

Abstract:

Cette thèse s’intéresse aux problématiques de routage dans les réseaux, notamment dans le graphe des systèmes autonomes (AS) d’Internet. Nous cherchons d’une part à mieux comprendre les propriétés du graphe de l’Internet qui sont utiles dans la conception de nouveaux paradigmes de routage. D’autre part, nous cherchons à évaluer par simulation les performances de ces paradigmes. La première partie de mes travaux porte sur l’étude d’une propriété́ métrique, l’hyperbolicité́ selon Gromov, utilisée dans la conception de nouveaux paradigmes de routage. Je présente dans un premier temps une nouvelle approche pour le calcul de l’hyperbolicité́ d’un graphe utilisant une décomposition du graphe par les cliques-séparatrices et la notion de paires éloignées. Je propose ensuite un nouvel algorithme pour le calcul de l’hyperbolicité́ qui, combiné avec la méthode de décomposition par les cliques-séparatrices, permet son calcul sur des graphes composés de 58 000 sommets en quelques heures. La deuxième partie de mes travaux porte sur le développement de DRMSim, une nouvelle plate-forme de simulation de modèles de routage dynamiques. Celle-ci permet l’évaluation des performances des schémas de routage et leur comparaison au protocole de référence, le protocole de routeur frontière, BGP. DRMSim a permis l’étude par simulation de différents schémas de routage compact sur des topologies à O(10k) nœuds. Je détaille l’architecture de DRMSim et quelques exemples d’utilisation. Puis, je présente une étude réalisée en vue de développer une version parallèle et distribuée de DRMSim dans le cadre de la simulation de BGP
This thesis considers routing issues in networks, and particularly the graph of the autonomous systems (AS) of the Internet. Firstly, we aim at better understanding the properties of the Internet that are useful in the design of new routing paradigms. Secondly, we want to evaluate by simulation the performance of these paradigms. The first part of my work concerns the study of the Gromov hyperbolicity, a useful metric property for the design of new routing paradigms. I show how to use a decomposition of the graph by clique-separators as a pre-processing method for the computation of the hyperbolicity. Then, I propose a new algorithm to compute this property. Altogether, these methods allows us for computing the hyperbolicity of graphs up to 58 000 nodes. The second part of my work concerns the development of DRMSim, a new Dynamic Routing Model Simulator. It facilitates the evaluation of the performances of various routing schemes and their comparison to the standard routing scheme of the Internet, the border router protocol BGP. Using DRMSim, we performed simulations of several compact routing schemes on topologies up to O(10k) nodes. I describe its architecture and detail some examples. Then, I present a feasibility study for the design of a parallel/distributed version of DRMSim in order to simulate BGP on larger topologies

APA, Harvard, Vancouver, ISO, and other styles

47

Newton, Matthew. "Sequential and parallel algorithms for low-crossing graph drawing." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/12944.

Full text

Abstract:

The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.

APA, Harvard, Vancouver, ISO, and other styles

48

Stewart, Anthony Graham. "Graph algorithms and complexity aspects on special graph classes." Thesis, Durham University, 2017. http://etheses.dur.ac.uk/12144/.

Full text

Abstract:

Graphs are a very flexible tool within mathematics, as such, numerous problems can be solved by formulating them as an instance of a graph. As a result, however, some of the structures found in real world problems may be lost in a more general graph. An example of this is the 4-Colouring problem which, as a graph problem, is NP-complete. However, when a map is converted into a graph, we observe that this graph has structural properties, namely being (K_5, K_{3,3})-minor-free which can be exploited and as such there exist algorithms which can find 4-colourings of maps in polynomial time. This thesis looks at problems which are NP-complete in general and determines the complexity of the problem when various restrictions are placed on the input, both for the purpose of finding tractable solutions for inputs which have certain structures, and to increase our understanding of the point at which a problem becomes NP-complete. This thesis looks at four problems over four chapters, the first being Parallel Knock-Out. This chapter will show that Parallel Knock-Out can be solved in O(n+m) time on P_4-free graphs, also known as cographs, however, remains hard on split graphs, a subclass of P_5-free graphs. From this a dichotomy is shown on $P_k$-free graphs for any fixed integer $k$. The second chapter looks at Minimal Disconnected Cut. Along with some smaller results, the main result in this chapter is another dichotomy theorem which states that Minimal Disconnected Cut is polynomial time solvable for 3-connected planar graphs but NP-hard for 2-connected planar graphs. The third chapter looks at Square Root. Whilst a number of results were found, the work in this thesis focuses on the Square Root problem when restricted to some classes of graphs with low clique number. The final chapter looks at Surjective H-Colouring. This chapter shows that Surjective H-Colouring is NP-complete, for any fixed, non-loop connected graph H with two reflexive vertices and for any fixed graph H’ which can be obtained from H by replacing vertices with true twins. This result enabled us to determine the complexity of Surjective H-Colouring on all fixed graphs H of size at most 4.

APA, Harvard, Vancouver, ISO, and other styles

49

Enciso, Rosa. "Alliances in Graphs: Parameterized Algorithms and on Partitioning Series-Parallel Graphs." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2479.

Full text

Abstract:

Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, |N∩S|≥|N-S|. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc . In , Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the "Satisfactory Graph Partitioning (SGP)" problem. In his dissertation , Shafique used the problem of partitioning a graph into alliances to model problems in data clustering. Decision problems for several types of alliances and alliance partitions have been shown to be NP-complete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in . In addition to parameterized algorithms for alliance related problems, we study the partition of series-parallel graphs into alliances. The class of series-parallel graphs is a special class in graph theory since many problems known to be NP-complete on general graphs have been shown to have polynomial time algorithms on series-parallel graphs. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to series-parallel graphs . Series-parallel graphs have also been to focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning series-parallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of series-parallel graphs that allow a partition into defensive alliances and a subclass of series-parallel graphs with a satisfactory partitions.
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD

APA, Harvard, Vancouver, ISO, and other styles

50

Pajak, Dominik. "Algorithms for Deterministic Parallel Graph Exploration." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2014. http://tel.archives-ouvertes.fr/tel-01064992.

Full text

Abstract:

Nous étudions dans cette thèse le problème de l'exploration parallèle d'un graphe à l'aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visitez les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe. Nous étudions d'abord l'exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les nœuds n'ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s'exécutent dans un minimum de temps possible pour polynomiale nombre d'agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l'impacte de différent méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire, mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes. Nous considérons également l'exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d'un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l'accélération défini comme la proportion entre le pire des cas de l'exploration d'un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d'agents. Nous présentons également des résultats optimaux sur l'accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes. Finalement nous considérons l'exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l'exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l'exploration des graphes.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Graph algorithmic'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles