To see the other types of publications on this topic, follow the link: Graph algorithmics.
Dissertations / Theses on the topic 'Graph algorithmics'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graph algorithmics.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Pitois, François. "Recherche de régularités et représentations succinctes de graphes." Electronic Thesis or Diss., Bourgogne Franche-Comté, 2024. http://www.theses.fr/2024UBFCK021.
Full textAbstract:
Dans cette thèse, nous étudions les régularités dans les graphes et les représentations succinctes des graphes. Une régularité, ou structure, est un terme générique qui désigne un ensemble de sommets du graphe ayant certaines propriétés. Parmi les régularités les plus connues, nous pouvons citer les cliques, les sous-graphes denses, les communautés, les modules et les splits. Une représentation succincte d'un graphe est une façon de le décrire qui est plus efficace que de simplement lister les différentes arêtes du graphe. Chercher des régularités permet d'obtenir des représentations succinctes. Ainsi, dans un premier temps, nous avons développé un algorithme de compression de graphe qui cherche différentes régularités du graphe, en sélectionne une partie et partitionne le graphe en fonction des structures sélectionnées. Cet algorithme donne une description succincte du graphe qui est meilleure que certains algorithmes de référence.Dans un deuxième temps, nous avons créé nos propres structures, de sorte qu'elles soient adaptées à la compression et qu'elles soient assez facile à chercher. Pour ce faire, nous sommes partis d'une structure connue, le split, et nous l'avons généralisée en créant le r-split, où r est un paramètre entier fixé. Nous avons alors montré que l'ensemble des r-splits d'un graphe a une cohérence globale, dans le sens où seul un nombre polynomial d'entre eux suffit à décrire l'intégralité des r-splits du graphe. Cela généralise une propriété bien connue des splits, pour lesquels seul un nombre linéaire d'entre eux suffit à retrouver tous les autres. Nous avons également montré que les r-splits peuvent se calculer en temps polynomial en utilisant des algorithmes d'optimisation de fonctions sous-modulaires.Dans un troisième temps, nous nous sommes intéressés à la recherche de structures particulières : les motifs dans les graphes ordonnés. Un graphe ordonné est un graphe dans lequel les sommets sont ordonnés de 1 à n. Un motif est un sous-graphe ordonné partiel, dans le sens où chaque paire de sommets peut être reliée soit par une arête, soit par une non-arête, soit par ni l'une ni l'autre. Le but est de fixer un motif P et de construire un algorithme capable de détecter si P est dans n'importe quel graphe ordonné donné en paramètre. Ce problème est polynomial en la taille du graphe via une recherche exhaustive. Cependant, est-il possible de faire mieux ? Nous avons montré que oui : la plupart des motifs à trois sommets peuvent être détectés en temps linéaire là où une recherche exhaustive nécessite un temps cubique. Concernant les motifs plus grands, nous avons exhibé des classes de motifs qui peuvent être détectés en temps sous-cubique : les motifs planaires extérieurs. En ajoutant des contraintes supplémentaires, nous avons exhibé une classe de motifs qui peuvent être détectée en temps linéaire : il s'agit des motifs planaires extérieurs sans cycle et sans non-arêteIn this thesis, we investigate regularities in graphs and succinct representations of graphs.A regularity, or structure, is a generic term that refers to a set of vertices in a graph with certain properties.Among the most well-known regularities, we can mention cliques, dense subgraphs, communities, modules, and splits.A succinct representation of a graph is a way of describing it that is more efficient than simply listing the different edges of the graph.Searching for regularities enables obtaining succinct representations.Thus, in a first step, we developed a graph compression algorithm that searches for different graph regularities, selects a portion of them, and partitions the graph based on the selected structures.This algorithm provides a succinct description of the graph that is better than some benchmark algorithms.In a second step, we created our own structures, so they are suitable for compression and are easy enough to search for.To do this, we started from a known structure, the split, and generalized it to create the r-split, where r is a fixed integer parameter.We then showed that the set of r-splits of a graph has a global coherence, in the sense that only a polynomial number of them is sufficient to describe all r-splits of the graph.This generalizes a well-known property of splits, for which only a linear number of them is sufficient to recover all the others.We also demonstrated that r-splits can be computed in polynomial time using submodular function optimization algorithms.In a third step, we focused on searching for particular regularities: patterns in ordered graphs.An ordered graph is a graph in which the vertices are ordered from 1 to n.A pattern is a partial ordered subgraph, in the sense that each pair of vertices can be connected either by an edge, a non-edge, or neither.The goal is to fix a pattern P and build an algorithm capable of detecting if P is in any ordered graph given as an input.This problem is polynomial in the size of the graph via exhaustive search.However, is it possible to do better?We were able to show that yes: most three-vertex patterns can be detected in linear time while exhaustive search requires cubic time.Regarding larger patterns, we exhibited classes of patterns that can be detected in subcubic time: outerplanar patterns.By adding additional constraints, we exhibited a class of patterns that can be detected in linear time: these are outerplanar patterns without cycles and non-edges
2
Dusart, Jérémie. "Graph searches with applications to cocomparability graphs." Paris 7, 2014. http://www.theses.fr/2014PA077048.
Full textAbstract:
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 grapheA 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
3
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 textAbstract:
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.
4
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 textAbstract:
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.
5
Dinh, Trong Hiêu. "Grammaires de graphes et langages formels." Phd thesis, Université Paris-Est, 2011. http://tel.archives-ouvertes.fr/tel-00665732.
Full textAbstract:
Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l'algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck
6
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 textAbstract:
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.
7
Duffy, Christopher. "Homomorphisms of (j, k)-mixed graphs." Thesis, Bordeaux, 2015. http://hdl.handle.net/1828/6601.
Full textAbstract:
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
8
Zhou, Hang. "Graph algorithms : network inference and planar graph optimization." Thesis, Paris, Ecole normale supérieure, 2015. http://www.theses.fr/2015ENSU0016/document.
Full textAbstract:
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 briquesThis 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
9
Sussfeld, Duncan. "Identifying remote homology and gene remodelling using network-based approaches." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASL112.
Full textAbstract:
L'augmentation toujours plus importante de données génomiques et métagénomiques appelle de nouveaux développements méthodologiques et bio-informatiques, afin de caractériser avec davantage de précision les phénomènes évolutifs dans leur ensemble. En particulier, certaines des méthodes usuelles pour étudier l'évolution des (familles de) gènes s'avèrent inadaptées lorsque la parenté entre séquences n'est que partiellement supportée. Ainsi, la définition et la reconstruction de familles de gènes se heurtent à l'obstacle de l'homologie distante, qui passe sous le seuil de détection des alignements de séquences. De même, les mécanismes d'évolution combinatoire, tels que les fusions et fissions de gènes, remettent en cause les représentations purement arborescentes de l'évolution des familles de gènes. L'application de méthodes complémentaires basées sur les réseaux de similarité de séquences permet de contourner certaines de ces lacunes, en proposant une représentation holistique des similarités entre gènes. La détection et l'analyse d'homologues très divergents de familles de gènes fortement conservées dans des jeux de données environnementaux est notamment facilitée par la recherche itérative d'homologie fondée sur les réseaux. Cette fouille itérative de métagénomes révèle une immense diversité de variants environnementaux dans ces familles, qui divergent de la diversité connue tant par leur séquence que par la structure des protéines qu'ils encodent, et elle permet de suggérer des pistes pour guider de futures explorations de la matière noire microbienne. En outre, en prenant en compte des liens d'homologie partielle entre séquences génétiques, les réseaux de similarité de séquences permettent une identification systématique des évènements de fusion et de fission de gènes. Il devient ainsi possible d'évaluer l'impact de ces processus au cours de l'évolution de lignées biologiques d'intérêt, permettant de comparer le rôle qu'ils ont joué lors de l'émergence de phénotypes multicellulaires complexes dans plusieurs telles lignées. Plus généralement, ces approches basées sur les réseaux illustrent l'intérêt de prendre en compte une pluralité de modèles pour étudier une plus grande variété de processus évolutifsThe ever-increasing accumulation of genomic and metagenomic data calls for new methodological developments in bioinformatics, in order to characterise evolutionary phenomena as a whole with better accuracy. In particular, some of the canonical methods to study the evolution of genes and gene families may be ill-suited when the relatedness of sequences is only partially supported. For instance, the definition and reconstruction of gene families face the hurdle of remote homology, which falls beneath the detection thresholds of sequence alignments. Likewise, combinatorial mechanisms of evolution, such as gene fusion and gene fission, challenge the purely tree-based representations of gene family evolution. The use of complementary methods based on sequence similarity networks allows us to circumvent some of these shortcomings, by offering a more holistic representation of similarities between genes. The detection and analysis of highly divergent homologues of strongly conserved families in environmental sequence datasets, in particular, is facilitated by iterative homology search protocols based on networks. This iterative mining of metagenomes reveals an immense diversity of environmental variants in these families, diverging from the known diversity in primary sequence as well as in the tertiary structure of the proteins they encode. It is thus able to suggest possible directions of future explorations into microbial dark matter. Furthermore, by factoring in relationships of partial homology between gene sequences, sequence similarity networks allow for a systematic identification of gene fusion and fission events. It thus becomes possible to assess the effects of these processes on the evolution of biological lineages of interest, enabling us for instance to compare the role that they played in the emergence of complex multicellular phenotypes between several such lineages. More generally, these network-based approaches illustrate the benefits of taking a plurality of models into account, in order to study a broader range of evolutionary processes
10
Slade, Michael L. "A layout algorithm for hierarchical graphs with constraints /." Online version of thesis, 1994. http://hdl.handle.net/1850/11724.
Full text
11
Bui, Thang Nguyen. "Graph bisection algorithms." Thesis, Massachusetts Institute of Technology, 1986. http://hdl.handle.net/1721.1/77680.
Full textAbstract:
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.
12
Despré, Vincent. "Topologie et algorithmes sur les cartes combinatoires." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM043/document.
Full textAbstract:
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 vueIn 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
13
Kanté, Mamadou Moustapha. "Graph structurings : some algorithmic applications." Thesis, Bordeaux 1, 2008. http://www.theses.fr/2008BOR13693/document.
Full textAbstract:
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
14
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
15
Profiti, Giuseppe <1980>. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/1/profiti_giuseppe_tesi.pdf.
Full textAbstract:
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.
16
Profiti, Giuseppe <1980>. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/.
Full textAbstract:
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.
17
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 textAbstract:
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.
18
Thiebaut, Jocelyn. "Algorithmic and structural results on directed cycles in dense digraphs." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS059.
Full textAbstract:
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 hamiltonienIn 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
19
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 textAbstract:
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.
20
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
21
Newton, Matthew. "Sequential and parallel algorithms for low-crossing graph drawing." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/12944.
Full textAbstract:
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.
22
Stewart, Anthony Graham. "Graph algorithms and complexity aspects on special graph classes." Thesis, Durham University, 2017. http://etheses.dur.ac.uk/12144/.
Full textAbstract:
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.
23
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 textAbstract:
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
24
Rocha, Leonardo Sampaio. "Algorithmic aspects of graph colouring heuristics." Nice, 2012. https://tel.archives-ouvertes.fr/tel-00759408.
Full textAbstract:
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 grapheA 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
25
Freeth, S. A. "Compression methods for graph algorithms." Thesis, University of Canterbury. Computer Science, 1985. http://hdl.handle.net/10092/9568.
Full textAbstract:
Two compression methods for representing graphs are presented, in conjunction with algorithms applying these methods. A decomposition technique for networks that can be generated in O(m) time is presented. The components of the decomposition and the shortest path matrix of the compressed network can be used to find the shortest path between any pair of vertices in the original network in linear time.
A compression method for boolean matrices and a method for applying the compression to boolean matrix multiplication is developed. The algorithms have an expected running time of O(n²*log ₂n). From this compression method a simple heuristic that may be applied to any algorithm for boolean matrix multiplication has been developed. This heuristic will improve the average running time of boolean matrix multiplication algorithms.
An order of magnitude analysis of the results published by Loukakis and Tsouris [1981], on the efficiency of algorithms for finding all maximal independent sets of a graph has been performed. This analysis showed that their conclusions, which are based on a direct comparison of the running times of the algorithms, do not take into account implementation factors.
An average constant factor improvement is developed for the algorithm of Tsukiyama, Ide, Ariyoshi and Shirakawa [1977] for finding all maximal independent sets of a graph.
Analysis of the running time results from the algorithm comparisons presented in this thesis show that the Bron-Kerbosch algorithm has the smallest rate of increase in running time as the size of the graphs increase.
26
Ren, Chenghui, and 任成會. "Algorithms for evolving graph analysis." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/197105.
Full textAbstract:
In many applications, entities and their relationships are represented by graphs. Examples include social networks (users and friendship), the WWW (web pages and hyperlinks) and bibliographic networks (authors and co-authorship). In a dynamic world, information changes and so the graphs representing the information evolve with time. For example, a Facebook link between two friends is established, or a hyperlink is added to a web page. We propose that historical graph-structured data be archived for analytical processing. We call a historical
evolving graph sequence an EGS.
We study the problem of efficient query processing on an EGS, which finds many applications that lead to interesting evolving graph analysis. To solve the problem, we propose a solution framework called FVF and a cluster-based LU decomposition algorithm called CLUDE, which can evaluate queries efficiently to support EGS analysis.
The Find-Verify-and-Fix (FVF) framework applies to a wide range of queries. We demonstrate how some important graph measures, including shortest-path distance, closeness centrality and graph centrality, can be efficiently computed from EGSs using FVF. Since an EGS generally contains numerous large graphs, we also discuss several compact storage models that support our FVF framework. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in EGS query processing.
A graph can be conveniently modeled by a matrix from which various quantitative measures are derived like PageRank and SALSA and Personalized PageRank and Random Walk with Restart. To compute these measures, linear systems of the form Ax = b, where A is a matrix that captures a graph's structure, need to be solved. To facilitate solving the linear system, the matrix A is often decomposed into two triangular matrices (L and U). In a dynamic world, the graph that models it changes with time and thus is the matrix A that represents the graph. We consider a sequence of evolving graphs and its associated sequence of evolving matrices. We study how LU-decomposition should be done over the sequence so that (1) the decomposition is efficient and (2) the resulting LU matrices best preserve the sparsity of the matrices A's (i.e., the number of extra non-zero entries introduced in L and U are minimized). We propose a cluster-based algorithm CLUDE for solving the problem. Through an experimental study, we show that CLUDE is about an order of magnitude faster than the traditional incremental update algorithm. The number of extra non-zero entries introduced by CLUDE is also about an order of magnitude fewer than that of the traditional algorithm. CLUDE is thus an efficient algorithm for LU decomposition that produces high-quality LU matrices over an evolving matrix sequence.published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
27
King, David Jonathan. "Functional programming and graph algorithms." Thesis, University of Glasgow, 1996. http://theses.gla.ac.uk/1629/.
Full textAbstract:
This thesis is an investigation of graph algorithms in the non-strict purely functional language Haskell. Emphasis is placed on the importance of achieving an asymptotic complexity as good as with conventional languages. This is achieved by using the monadic model for including actions on the state. Work on the monadic model was carried out at Glasgow University by Wadler, Peyton Jones, and Launchbury in the early nineties and has opened up many diverse application areas. One area is the ability to express data structures that require sharing. Although graphs are not presented in this style, data structures that graph algorithms use are expressed in this style. Several examples of stateful algorithms are given including union/find for disjoint sets, and the linear time sort binsort. The graph algorithms presented are not new, but are traditional algorithms recast in a functional setting. Examples include strongly connected components, biconnected components, Kruskal's minimum cost spanning tree, and Dijkstra's shortest paths. The presentation is lucid giving more insight than usual. The functional setting allows for complete calculational style correctness proofs - which is demonstrated with many examples. The benefits of using a functional language for expressing graph algorithms are quantified by looking at the issues of execution times, asymptotic complexity, correctness, and clarity, in comparison with traditional approaches. The intention is to be as objective as possible, pointing out both the weaknesses and the strengths of using a functional language.
28
He, Dayu. "Algorithms for Graph Drawing Problems." Thesis, State University of New York at Buffalo, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10284151.
Full textAbstract:
A graph G is called planar if it can be drawn on the plan such that no two distinct edges intersect each other but at common endpoints. Such drawing is called a plane embedding of G. A plane graph is a graph with a fixed embedding. A straight-line drawing G of a graph G = (V, E) is a drawing where each vertex of V is drawn as a distinct point on the plane and each edge of G is drawn as a line segment connecting two end vertices. In this thesis, we study a set of planar graph drawing problems.
First, we consider the problem of monotone drawing: A path P in a straight line drawing Γ is monotone if there exists a line l such that the orthogonal projections of the vertices of P on l appear along l in the order they appear in P. We call l a monotone line (or monotone direction) of P. G is called a monotone drawing of G if it contains at least one monotone path Puw between every pair of vertices u,w of G. Monotone drawings were recently introduced by Angelini et al. and represent a new visualization paradigm, and is also closely related to several other important graph drawing problems. As in many graph drawing problems, one of the main concerns of this research is to reduce the drawing size, which is the size of the smallest integer grid such that every graph in the graph class can be drawn in such a grid. We present two approaches for the problem of monotone drawings of trees. Our first approach show that every n-vertex tree T admits a monotone drawing on a grid of size O(n1.205) × O( n1.205) grid. Our second approach further reduces the size of drawing to 12n × 12n, which is asymptotically optimal. Both of our two drawings can be constructed in O(n) time.
We also consider monotone drawings of 3-connected plane graphs. We prove that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a f × f grid, which can be constructed in O(n) time.
Second, we consider the problem of orthogonal drawing. An orthogonal drawing of a plane graph G is a planar drawing of G such that each vertex of G is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. Orthogonal drawing has attracted much attention due to its various applications in circuit schematics, relationship diagrams, data flow diagrams etc. . Rahman et al. gave a necessary and sufficient condition for a plane graph G of maximum degree 3 to have an orthogonal drawing without bends. An orthogonal drawing D(G) is orthogonally convex if all faces of D(G) are orthogonally convex polygons. Chang et al. gave a necessary and sufficient condition (which strengthens the conditions in the previous result) for a plane graph G of maximum degree 3 to have an orthogonal convex drawing without bends. We further strengthen the results such that if G satisfies the same conditions as in previous papers, it not only has an orthogonally convex drawing, but also a stronger star-shaped orthogonal drawing.
29
Capresi, Chiara. "Algorithms for identifying clusters in temporal graphs and realising distance matrices by unicyclic graphs." Doctoral thesis, Università di Siena, 2022. http://hdl.handle.net/11365/1211314.
Full textAbstract:
In this thesis I present some results, which mainly concern finding algorithms for graphs problems, to which I worked on during my Ph.D with the supervision of my supervisors. In particular, as a first theme, it is presented a new temporal interpretation of the well studied \ClusterEditing which we called \EditTempClique (\ETC). In this regard, %at first it is shown that the corresponding versions in the temporal setting of any \NP-Hard version of \ClusterEditing is still \NP-Hard. Then,
in this work, it is proved that \ETC is \NP-Complete even if we restrict the possible inputs to the class of temporal graphs with a path as their underlying graph. Furthermore, it is presented a result that shows that \ETC is instead tractable in polynomial time if the underlying graph is a path and the maximum number of appearances allowed for each of the edges of that path is fixed.
Taking in mind the known key observation that a static graph is a cluster graph if and only if it does not contain any induced $P_3$, it is presented a local characterisation for cluster temporal graphs. This characterisation establishes that a temporal graph is a cluster temporal graph if and only if every subset of at most five vertices induces a cluster temporal graph. Using this characterisation, we obtain an \FPT~algorithm for \ETC parameterised simultaneously by the number of modifications and the lifetime (number of timesteps) of the input temporal graph. Furthermore, it is shown via a counterexample, that a cluster temporal graph can not be properly characterised by sets of at most four vertices.
In the last Chapter of this thesis, at first it is proven a result on the realisation of distance matrices by $n-$cycles and then it is developed an algorithm that allows to establish if a given distance matrix $D$ can or cannot be realised by a weighted unicyclic graph or at least by a weighted tree. In case of affirmative answer, a second part of the algorithm reconstructs that graph. The algorithm takes $\mathcal O(n^4)$. Furthermore, it is shown that if the algorithm returns a unicyclic graph as a realisation of $D$, then this realisation is optimal.
30
Creusefond, Jean. "Caractériser et détecter les communautés dans les réseaux sociaux." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMC203/document.
Full textAbstract:
Dans cette thèse, je commence par présenter une nouvelle caractérisation des communautés à partir d'un réseau de messages inscrits dans le temps. Je montre que la structure de ce réseau a un lien avec les communautés : on trouve majoritairement des échanges d'information à l'intérieur des communautés tandis que les frontières servent à la diffusion.Je propose ensuite d'évaluer les communautés par la vitesse de propagation des communications qui s'y déroulent avec une nouvelle fonction de qualité : la compacité. J'y présente aussi un algorithme de détection de communautés, le Lex-Clustering, basé sur un algorithme de parcours de graphe qui reproduit des caractéristiques des modèles de diffusion d'information. Enfin, je présente une méthodologie permettant de faire le lien entre les fonctions de qualité et les vérités de terrain. J'introduis le concept de contexte, des ensembles de vérités de terrain qui présentente des ressemblances. Je mets à disposition un logiciel nommé CoDACom (Community Detection Algorithm Comparator, codacom.greyc.fr) permettant d'appliquer cette méthodologie ainsi que d'utiliser un grand nombre d'outils de détection de communautésN this thesis, I first present a new way of characterising communities from a network of timestamped messages. I show that its structure is linked with communities : communication structures are over-represented inside communities while diffusion structures appear mainly on the boundaries.Then, I propose to evaluate communities with a new quality function, compacity, that measures the propagation speed of communications in communities. I also present the Lex-Clustering, a new community detection algorithm based on the LexDFS graph traversal that features some characteristics of information diffusion.Finally, I present a methodology that I used to link quality functions and ground-truths. I introduce the concept of contexts, sets of ground-truths that are similar in some way. I implemented this methodology in a software called CoDACom (Community Detection Algorithm Comparator, codacom.greyc.fr) that also provides many community detection tools
31
Durand, de Gevigney Olivier. "Orientations des graphes : structures et algorithmes." Thesis, Grenoble, 2013. http://www.theses.fr/2013GRENM027/document.
Full textAbstract:
Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-completOrienting an undirected graph means replacing each edge by an arc with the same ends. We investigate the connectivity of the resulting directed graph. Orientations with arc-connectivity constraints are now deeply understood but very few results are known in terms of vertex-connectivity. Thomassen conjectured that sufficiently highly vertex-connected graphs have a k-vertex- connected orientation while Frank conjectured a characterization of the graphs admitting such an orientation. The results of this thesis are structures around the concepts of orientation, packing, connectivity and matroid. First, we disprove a conjecture of Recski on decomposing a graph into trees having orientations with specified indegrees. We also prove a new result on packing rooted arborescences with matroid constraints. This generalizes a fundamental result of Edmonds. Moreover, we show a new packing theorem for the bases of count matroids that induces an improvement of the only known result on Thomassen's conjecture. Secondly, we give a construction and an augmentation theorem for a family of graphs related to Frank's conjecture. To conclude, we disprove the conjecture of Frank and prove that, for every integer k >= 3, the problem of deciding whether a graph admits a k-vertex-orientation is NP-complete
32
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 textAbstract:
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éeSince 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
33
Rinke, Sebastian. "Analysis and Adaption of Graph Mapping Algorithms for Regular Graph Topologies." Master's thesis, Universitätsbibliothek Chemnitz, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200901453.
Full textAbstract:
The Message Passing Interface (MPI) standard defines virtual topologies that can be applied to systems
of cooperating processes. Among issues regarding a more convenient namespace this may be used to
optimize the placement of MPI processes in order to reduce communication time. That means, the
processes with their main communication paths represent a graph that has to be cost efficiently mapped
onto the graph representing the actual communication network. In this context, this work analyses
and compares state-of-the-art task mapping strategies with respect to running time and their quality
of solutions to the MPI mapping problem. In particular, the focus is on generic strategies that can
be used for arbitrary process/network topologies although, here, the topologies of interest are regular
ones, where the number of processes is greater than the number of processors in the underlying physical
network. Additionally, different measures of mapping quality are discussed and a close correspondence
between the most appropriate, the weighted edge cut, and program execution time is shown. In order
to investigate how mapping quality affects MPI program execution time, some mapping strategies have
been incorporated into Open MPI. Finally, benchmark results prove that optimized process-to-processor
mappings can improve program execution time by up to 60%, compared to the default mapping in many
MPI implementations (linear mapping). The findings in this work can serve as reference not only for MPI
implementors, but also for researchers investigating static process-to-processor mappings, in general.
34
Sivanathan, Gowrishankar. "Sink free orientations in a graph." Diss., Online access via UMI:, 2009.
Find full text
35
Maceli, Peter Lawson. "Deciding st-connectivity in undirected graphs using logarithmic space." Columbus, Ohio : Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1211753530.
Full text
36
Deel, Troy A. "A statistical study of graph algorithms." Virtual Press, 1985. http://liblink.bsu.edu/uhtbin/catkey/424871.
Full textAbstract:
The object of this paper is to investigate the behavior of some important graph properties and to statistically analyze the execution times of certain graph are the average degree of a vertex, connectivity of a graph, the existence of Hamilton cycles, Euler tours, and bipartitions in graphs. This study is unique in that it is based on statistical rather than deterministic methods.
37
Anderson, Jon K. "Genetic algorithms applied to graph theory." Virtual Press, 1999. http://liblink.bsu.edu/uhtbin/catkey/1136714.
Full textAbstract:
This thesis proposes two new variations on the genetic algorithm. The first attempts to improve clustering problems by optimizing the structure of a genetic string dynamically during the run of the algorithm. This is done by using a permutation on the allele which is inherited by the next generation. The second is a multiple pool technique which ensures continuing convergence by maintaining unique lineages and merging pools of similar age. These variations will be tested against two well-known graph theory problems, the Traveling Salesman Problem and the Maximum Clique Problem. The results will be analyzed with respect to string rates, child improvement, pool rating resolution, and average string age.Department of Computer Science
38
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 textAbstract:
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.
39
Newman, Alantha. "Algorithms for string and graph layout." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/28745.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.Includes bibliographical references (p. 121-125).
Many graph optimization problems can be viewed as graph layout problems. A layout of a graph is a geometric arrangement of the vertices subject to given constraints. For example, the vertices of a graph can be arranged on a line or a circle, on a two- or three-dimensional lattice, etc. The goal is usually to place all the vertices so as to optimize some specified objective function. We develop combinatorial methods as well as models based on linear and semidefinite programming for graph layout problems. We apply these techniques to some well-known optimization problems. In particular, we give improved approximation algorithms for the string folding problem on the two- and three-dimensional square lattices. This combinatorial graph problem is motivated by the protein folding problem, which is central in computational biology. We then present a new semidefinite programming formulation for the linear ordering problem (also known as the maximum acyclic subgraph problem) and show that it provides an improved bound on the value of an optimal solution for random graphs. This is the first relaxation that improves on the trivial "all edges" bound for random graphs.
by Alantha Newman.
Ph.D.
40
Yodpinyanee, Anak. "Sub-linear algorithms for graph problems." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120411.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 189-199).
In the face of massive data sets, classical algorithmic models, where the algorithm reads the entire input, performs a full computation, then reports the entire output, are rendered infeasible. To handle these data sets, alternative algorithmic models are suggested to solve problems under the restricted, namely sub-linear, resources such as time, memory or randomness. This thesis aims at addressing these limitations on graph problems and combinatorial optimization problems through a number of different models. First, we consider the graph spanner problem in the local computation algorithm (LCA) model. A graph spanner is a subgraph of the input graph that preserves all pairwise distances up to a small multiplicative stretch. Given a query edge from the input graph, the LCA explores a sub-linear portion of the input graph, then decides whether to include this edge in its spanner or not - the answers to all edge queries constitute the output of the LCA. We provide the first LCA constructions for 3 and 5-spanners of general graphs with almost optimal trade-offs between spanner sizes and stretches, and for fixed-stretch spanners of low maximum-degree graphs. Next, we study the set cover problem in the oracle access model. The algorithm accesses a sub-linear portion of the input set system by probing for elements in a set, and for sets containing an element, then computes an approximate minimum set cover: a collection of an approximately-minimum number of sets whose union includes all elements. We provide probe-efficient algorithms for set cover, and complement our results with almost tight lower bound constructions. We further extend our study to the LP-relaxation variants and to the streaming setting, obtaining the first streaming results for the fractional set cover problem. Lastly, we design local-access generators for a collection of fundamental random graph models. We demonstrate how to generate graphs according to the desired probability distribution in an on-the-fly fashion. Our algorithms receive probes about arbitrary parts of the input graph, then construct just enough of the graph to answer these probes, using only polylogarithmic time, additional space and random bits per probe. We also provide the first implementation of random neighbor probes, which is a basic algorithmic building block with applications in various huge graph models.
by Anak Yodpinyanee.
Ph. D.
41
Sun, Jiankai. "Directed Graph Analysis: Algorithms and Applications." The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1565797455907422.
Full text
42
Ren, Jintong. "Optimization algorithms for graph layout problems." Thesis, Angers, 2020. https://tel.archives-ouvertes.fr/tel-03178385.
Full textAbstract:
Cette thèse considère deux problèmes de disposition des graphes : le problème de la bande passante cyclique (CBP) et le problème de l’agencement linéaire minimum (MinLA). Le CBP est une extension naturelle du problème de minimisation de la bande passante (BMP) et le MinLA est un problème de somme minimale. Ces problèmes sont largement appliqués dans la vie réelle. Puisqu’ils sont NP-difficile, il est difficile de les résoudre dans le cas général. Par conséquent, cette thèse est consacrée au développement d’algorithmes heuristiques efficaces pour faire face à ces problèmes. Plus précisément, nous introduisons deux algorithmes de recherche locale itétée, un algorithme mémétique avec différents opérateurs de recombinaison pour le CBP et une heuristique de voisinage basée sur un ensemble pour résoudre le MinLA. On montre expérimentalement que pour le CBP, les deux algorithmes de recherche locale itéré pouvaient concurrencer favorablement les méthodes de l’état de l’art, le croisement approprié est identifié pour l’algorithme mémétique. On montre également que pour le MinLA, l’heuristique de voisinage basée sur l’ensemble s’est avérée plus efficace que des algorithmes avec voisinage traditionnel à 2-flipThis thesis considers two graph layout problems: the cyclic bandwidth problem (CBP) and the minimum linear arrangement problem (MinLA). The CBP is a natural extension of the bandwidth minimization problem (BMP) and the MinLA is a min-sum problem. These problems are widely applied in the real life. Since they are NP-hard problems, it is computational difficult to solve them in the general case. Therefore, this thesis is dedicated to developing effective heuristic algorithms to deal with these challenging problems.Specifically, we introduce two iterated local search algorithms, a memetic algorithm with different recombination operators for the CBP and a set based neighborhood heuristic algorithm to solve the MinLA. The two iterated local search algorithms are experimentallydemonstrated to be able to compete favourably with state-of-the-art methods, the feature of a suitable crossover for the memetic algorithm is identified for the CBP and the set based neighborhood heuristic algorithm is proven to be more efficient than the traditional 2-flip neighborhood algorithm
43
Neggazi, Brahim. "Self-stabilizing algorithms for graph parameters." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10041/document.
Full textAbstract:
Le concept d'auto-stabilisation a été introduit par Dijkstra en 1973. Un système distribué est auto-stabilisant s'il peut démarrer de n'importe quelle configuration initiale et retrouver une configuration légitime en un temps fini par lui-même et sans aucune intervention extérieure. La convergence est également garantie lorsque le système est affecté par des fautes transitoires, ce qui en fait une approche élégante, non masquante, pour la tolérance aux pannes. L'auto-stabilisation a été étudiée dans divers domaines des systèmes distribués tels que les problèmes de synchronisation de l'horloge, de la communication et les protocoles de routage. Vu l'importance des paramètres de graphes notamment pour l'organisation et l'optimisation des communications dans les réseaux et les systèmes distribués, plusieurs algorithmes auto-stabilisants pour des paramètres de graphe ont été proposés dans la littérature, tels que les algorithmes autostabilisants permettant de trouver les ensembles dominants minimaux, coloration des graphes, couplage maximal et arbres de recouvrement. Dans cette perspective, nous proposons, dans cette thèse, des algorithmes distribués et autostabilisants pour certains problèmes de graphes bien connus, en particulier pour les décompositions de graphes et les ensembles dominants qui n'ont pas encore été abordés avec le concept de l'autostabilisation. Les quatre problèmes majeurs considérés dans cette thèse sont: partitionnement en triangles, décomposition en p-étoiles, Monitoring des arêtes, fort ensemble dominant et indépendant. Ainsi, le point commun entre ces problèmes, est qu'ils sont tous considérés comme des variantes des problèmes de domination et de couplage dans les graphes et leur traitement se fait d'une manière auto-stabilisanteThe concept of self-stabilization was first introduced by Dijkstra in 1973. A distributed system is self-stabilizing if it can start from any possible configuration and converges to a desired configuration in finite time by itself without using any external intervention. Convergence is also guaranteed when the system is affected by transient faults. This makes self-stabilization an effective approach for non-masking fault-tolerance. The self-stabilization was studied in various fields in distributed systems such as the problems of clock synchronization, communication and routing protocols. Given the importance of graph parameters, especially for organization and communication of networks and distributed systems, several self-stabilizing algorithms for classic graph parameters have been developed in this direction, such as self-stabilizing algorithms for finding minimal dominating sets, coloring, maximal matching, spanning tree and so on. Thence, we propose in this thesis, distributed and self-stabilizing algorithms to some wellknown graphs problems, particularly for graph decompositions and dominating sets problems that have not yet been addressed in a view of self-stabilization. The four major problems considered in this thesis are: the partitioning into triangles, p-star decomposition, edge monitoring set and independent strong dominating set problems. The common point between these four problems is that they are considered as variants of dominating set and matching problems and all propositions deal with the self-stabilization paradigm
44
Sun, Wen. "Heuristic Algorithms for Graph Coloring Problems." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0027/document.
Full textAbstract:
Cette thèse concerne quatre problèmes de coloration de graphes NPdifficiles, à savoir le problème de coloration (GCP), le problème de coloration équitable (ECP), le problème de coloration des sommets pondérés et le problème de sous-graphe critique (k-VCS). Ces problèmes sont largement étudiés dans la littérature, non seulement pour leur difficulté théorique, mais aussi pour leurs applications réelles dans de nombreux domaines. Étant donné qu'ils appartiennent à la classe de problèmes NP-difficiles, il est difficile de les résoudre dans le cas général de manière exacte. Pour cette raison, cette thèse est consacrée au développement d'approches heuristiques pour aborder ces problèmes complexes. Plus précisément, nous développons un algorithme mémétique de réduction (RMA) pour la coloration des graphes, un algorithme de recherche réalisable et irréalisable (FISA) pour la coloration équitable et un réalisable et irréalisable (AFISA) pour le problème de coloration des sommets pondérés et un algorithme de suppression basé sur le retour en arrière (IBR) pour le problème k-VCS. Tous les algorithmes ont été expérimentalement évalués et comparés aux méthodes de l'état de l'artThis thesis concerns four NP-hard graph coloring problems, namely, graph coloring (GCP), equitable coloring (ECP), weighted vertex coloring (WVCP) and k-vertex-critical subgraphs (k-VCS). These problems are extensively studied in the literature not only for their theoretical intractability, but also for their real-world applications in many domains. Given that they belong to the class of NP-hard problems, it is computationally difficult to solve them exactly in the general case. For this reason, this thesis is devoted to developing effective heuristic approaches to tackle these challenging problems. We develop a reduction memetic algorithm (RMA) for the graph coloring problem, a feasible and infeasible search algorithm (FISA) for the equitable coloring problem, an adaptive feasible and infeasible search algorithm (AFISA) for the weighted vertex coloring problem and an iterated backtrack-based removal (IBR) algorithm for the k-VCS problem. All these algorithms were experimentally evaluated and compared with state-of-the-art methods
45
Peternek, Fabian Hans Adolf. "Graph compression using graph grammars." Thesis, University of Edinburgh, 2018. http://hdl.handle.net/1842/31094.
Full textAbstract:
This thesis presents work done on compressed graph representations via hyperedge replacement grammars. It comprises two main parts. Firstly the RePair compression scheme, known for strings and trees, is generalized to graphs using graph grammars. Given an object, the scheme produces a small context-free grammar generating the object (called a “straight-line grammar”). The theoretical foundations of this generalization are presented, followed by a description of a prototype implementation. This implementation is then evaluated on real-world and synthetic graphs. The experiments show that several graphs can be compressed stronger by the new method, than by current state-of-the-art approaches. The second part considers algorithmic questions of straight-line graph grammars. Two algorithms are presented to traverse the graph represented by such a grammar. Both algorithms have advantages and disadvantages: the first one works with any grammar but its runtime per traversal step is dependent on the input grammar. The second algorithm only needs constant time per traversal step, but works for a restricted class of grammars and requires quadratic preprocessing time and space. Finally speed-up algorithms are considered. These are algorithms that can decide specific problems in time depending only on the size of the compressed representation, and might thus be faster than a traditional algorithm would on the decompressed structure. The idea of such algorithms is to reuse computation already done for the rules of the grammar. The possible speed-ups achieved this way is proportional to the compression ratio of the grammar. The main results here are a method to answer “regular path queries”, and to decide whether two grammars generate isomorphic trees.
46
Rannou, Léo. "Temporal Connectivity and Path Computation for Stream Graph." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS418.
Full textAbstract:
Les données structurelles et les données temporelles ont, pendant longtemps, été analysées séparément. De nombreux réseaux complexes contiennent une dimension temporelle, comme les contacts entre individus ou les transactions financières. La théorie des graphes fournit un large ensemble d'outils pour modéliser et analyser les connexions entre entités. Malheureusement, cette approche ne prend pas compte la nature temporelle des interactions. La théorie des stream graphs est un formalisme permettant de modéliser les réseaux dynamiques dans lesquels les nœuds et/ou les liens arrivent et/ou partent au fil du temps. Plusieurs concepts théoriques tels que les composantes connexes dans les stream graphs ont été définis récemment, mais aucun algorithme n'a été proposé pour les calculer. De plus, la complexité algorithmique de ces problèmes est inconnue, ainsi que les connaissances qu'ils peuvent apporter sur les stream graphs de terrain. Dans cette thèse, nous proposons plusieurs solutions pour le calcul de notions de connectivité et de chemins dans les stream graphs. Nous présentons également des représentations alternatives - des structures de données conçues pour faciliter certains calculs - stream graphs. Nous fournissons également des implémentations et comparons expérimentalement nos méthodes sur une grande variété de cas pratiques. Nous montrons que ces concepts apportent beaucoup d'informations sur les caractéristiques de ces ensembles de données. Straph, une bibliothèque python, a été développée afin de disposer d'une ressource fiable afin de manipuler, analyser et visualiser les stream graphsFor a long time, structured data and temporal data have been analysed separately. Many real world complex networks have a temporal dimension, such as contacts between individuals or financial transactions. Graph theory provides a wide set of tools to model and analyze static connections between entities. Unfortunately, this approach does not take into account the temporal nature of interactions. Stream graph theory is a formalism to model highly dynamic networks in which nodes and/or links arrive and/or leave over time. The number of applications of stream graph theory has risen rapidly, along with the number of theoretical concepts and algorithms to compute them. Several theoretical concepts such as connected components and temporal paths in stream graphs were defined recently, but no algorithm was provided to compute them. Moreover, the algorithmic complexities of these problems are unknown, as well as the insight they may shed on real-world stream graphs of interest. In this thesis, we present several solutions to compute notions of connectivity and path concepts in stream graphs. We also present alternative representations - data structures designed to facilitate specific computations - of stream graphs. We provide implementations and experimentally compare our methods in a wide range of practical cases. We show that these concepts indeed give much insight on features of large-scale datasets. Straph, a python library, was developed in order to have a reliable library for manipulating, analysing and visualising stream graphs, to design algorithms and models, and to rapidly evaluate them
47
Pham, Hong Phong. "Studies on Optimal Colorful Structures in Vertex-Colored Graphs." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS528.
Full textAbstract:
Dans cette thèse, nous étudions des problèmes différents de coloration maximale dans les graphes sommet-colorés. Nous nous concentrons sur la recherche des structures avec le nombre maximal possible de couleurs par des algorithmes en temps polynomial, nous donnons aussi la preuve des problèmes NP-difficiles pour des graphes spécifiques. En particulier, nous étudions d’abord le problème de l’appariement coloré maximum. Nous montrons que ce problème peut être résolu efficacement en temps polynomial. En plus, nous considérons également une version spécifique de ce problème, à savoir l’appariement tropical, qui consiste à trouver un appariement contenant toutes les couleurs du graphe original. De même, un algorithme de temps polynomial est également fourni pour le problème de l’appariement tropical avec la cardinalité minimale et le problème de l’appariement tropical maximum avec la cardinalité minimale. Ensuite, nous étudions le problème des chemins colorés maximum. Il existe deux versions pour ce problème: le problème de plus court chemin tropical, c’est-à-dire de trouver un chemin tropical avec le poids total minimum et le problème de plus longue chemin coloré, à savoir, trouver un chemin avec un nombre maximum possible de couleurs. Nous montrons que les deux versions de ce problème sont NP-difficile pour un graphe orienté acyclique, graphes de cactus et graphes d'intervalles où le problème de plus long chemin est facile. De plus, nous fournissons également un algorithme de paramètre fixe pour le premier dans les graphes généraux et plusieurs algorithmes de temps polynomiaux pour le second dans les graphes spécifiques, y compris les graphes des chaîne bipartites, graphes de seuil, arborescences, graphes des blocs et graphes d'intervalles appropriés. Ensuite, nous considérons le problème des cycles colorés maximum. Nous montrons d'abord que le problème est NP-difficile même pour des graphes simples tels que des graphes divisés, des graphes bi-connecteurs et des graphes d'intervalles. Nous fournissons ensuite des algorithmes de temps polynomial pour les classes de graphes de seuil et graphes des chaîne bipartites et graphes d'intervalles appropriés. Plus tard, nous étudions le problème des cliques colorées maximum. Nous montrons tout d’abord que le problème est NP-difficile même pour plusieurs cas où le problème de clique maximum est facile, comme des graphes complémentaires des graphes de permutation bipartite, des graphes complémentaires de graphes convexes bipartites et des graphes de disques unitaires, et aussi pour des graphes sommet-colorées appropriés. Ensuite, nous proposons un algorithme paramétré XP et des algorithmes de temps polynomial pour les classes de graphes complémentaires de graphes en chaîne bipartites, des graphes multipartites complets et des graphes complémentaires de graphes cycles. Enfin, nous nous concentrons sur le problème des stables (ensembles indépendants) colorés maximum. Nous montrons d’abord que le problème est NP-difficile même dans certains cas où le problème de stable maximum est facile, tels que les co-graphes et les graphes des P₅-gratuit. Ensuite, nous fournissons des algorithmes de temps polynomial pour les graphes de grappes, et les arbresIn this thesis, we study different maximum colorful problems in vertex-colored graphs. We focus on finding structures with the possible maximum number of colors by efficient polynomial-time algorithms, or prove these problems as NP-hard for specific graphs. In particular, we first study the maximum colorful matching problem. We show that this problem can be efficiently solved in polynomial time. Moreover, we also consider a specific version of this problem, namely tropical matching, that is to find a matching containing all colors of the original graph, if any. Similarly, a polynomial time algorithm is also provided for the problem of tropical matching with the minimum cardinality and the problem of maximal tropical matching with the minimum cardinality. Then, we study the maximum colorful paths problem. There are two versions for this problem: the shortest tropical path problem, i.e., finding a tropical path with the minimum total weight, and the maximum colorful path problem, i.e., finding a path with the maximum number of colors possible. We show that both versions of this problem are NP-hard for directed acyclic graphs, cactus graphs and interval graphs where the longest path problem is easy. Moreover, we also provide a fixed parameter algorithm for the former in general graphs and several polynomial time algorithms for the latter in specific graphs, including bipartite chain graphs, threshold graphs, trees, block graphs, and proper interval graphs. Next we consider the maximum colorful cycles problem. We first show that the problem is NP-hard even for simple graphs such as split graphs, biconnected graphs, interval graphs. Then we provide polynomial-time algorithms for classes of threshold graphs and bipartite chain graphs and proper interval graphs. Later, we study the maximum colorful cliques problem. We first show that the problem is NP-hard even for several cases where the maximum clique problem is easy, such as complement graphs of bipartite permutation graphs, complement graphs of bipartite convex graphs, and unit disk graphs, and also for properly vertex-colored graphs. Next, we propose a XP parameterized algorithm and polynomial-time algorithms for classes of complement graphs of bipartite chain graphs, complete multipartite graphs and complement graphs of cycle graphs. Finally, we focus on the maximum colorful independent set problem. We first prove that the problem is NP-hard even for some cases where the maximum independent set problem is easy, such as cographs and P₅-free graphs. Next, we provide polynomial time algorithms for cluster graphs and trees
48
Santacruz, Muñoz José Luis. "Error-tolerant Graph Matching on Huge Graphs and Learning Strategies on the Edit Costs." Doctoral thesis, Universitat Rovira i Virgili, 2019. http://hdl.handle.net/10803/668356.
Full textAbstract:
Els grafs són estructures de dades abstractes que s'utilitzen per a modelar problemes reals amb dues entitats bàsiques: nodes i arestes. Cada node o vèrtex representa un punt d'interès rellevant d'un problema, i cada aresta representa la relació entre aquests vèrtexs. Els nodes i les arestes podrien incorporar atributs per augmentar la precisió del problema modelat. Degut a aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per computador, biomèdics, anàlisi de xarxes, etc. La Distància d'edició de grafs (GED) s'ha convertit en una eina important en el reconeixement de patrons estructurals, ja que permet mesurar la dissimilitud dels grafs.
A la primera part d'aquesta tesi es presenta un mètode per generar una parella grafs juntament amb la seva correspondència en un cost computacional lineal. A continuació, se centra en com mesurar la dissimilitud entre dos grafs enormes (més de 10.000 nodes), utilitzant un nou algoritme de aparellament de grafs anomenat Belief Propagation. Té un cost computacional O(d^3.5N). Aquesta tesi també presenta un marc general per aprendre els costos d'edició implicats en els càlculs de la GED automàticament. Després, concretem aquest marc en dos models diferents basats en xarxes neuronals i funcions de densitat de probabilitat. S'ha realitzat una validació pràctica exhaustiva en 14 bases de dades públiques. Aquesta validació mostra que la precisió és major amb els costos d'edició apresos, que amb alguns costos impostos manualment o altres costos apresos automàticament per mètodes anteriors. Finalment proposem una aplicació de l'algoritme Belief propagation utilitzat en la simulació de la mecànica muscular.Los grafos son estructuras de datos abstractos que se utilizan para modelar problemas reales con dos entidades básicas: nodos y aristas. Cada nodo o vértice representa un punto de interés relevante de un problema, y cada arista representa la relación entre estos vértices. Los nodos y las aristas podrían incorporar atributos para aumentar la precisión del problema modelado. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como la visión por computador, biomédicos, análisis de redes, etc. La Distancia de edición de grafos (GED) se ha convertido en una herramienta importante en el reconocimiento de patrones estructurales, ya que permite medir la disimilitud de los grafos. En la primera parte de esta tesis se presenta un método para generar una pareja grafos junto con su correspondencia en un coste computacional lineal. A continuación, se centra en cómo medir la disimilitud entre dos grafos enormes (más de 10.000 nodos), utilizando un nuevo algoritmo de emparejamiento de grafos llamado Belief Propagation. Tiene un coste computacional O(d^3.5n). Esta tesis también presenta un marco general para aprender los costos de edición implicados en los cálculos de GED automáticamente. Luego, concretamos este marco en dos modelos diferentes basados en redes neuronales y funciones de densidad de probabilidad. Se ha realizado una validación práctica exhaustiva en 14 bases de datos públicas. Esta validación muestra que la precisión es mayor con los costos de edición aprendidos, que con algunos costos impuestos manualmente u otros costos aprendidos automáticamente por métodos anteriores. Finalmente proponemos una aplicación del algoritmo Belief propagation utilizado en la simulación de la mecánica muscular.
Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the modeled problem, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, bio-medics, network analysis, etc. Graph Edit Distance (GED) has become an important tool in structural pattern recognition since it allows to measure the dissimilarity of attributed graphs. The first part presents a method is presented to generate graphs together with an upper and lower bound distance and a correspondence in a linear computational cost. Through this method, the behaviour of the known -or the new- sub-optimal Error-Tolerant graph matching algorithm can be tested against a lower and an upper bound GED on large graphs, even though we do not have the true distance. Next, the present is focused on how to measure the dissimilarity between two huge graphs (more than 10.000 nodes), using a new Error-Tolerant graph matching algorithm called Belief Propagation algorithm. It has a O(d^3.5n) computational cost.This thesis also presents a general framework to learn the edit costs involved in the GED calculations automatically. Then, we concretise this framework in two different models based on neural networks and probability density functions. An exhaustive practical validation on 14 public databases has been performed. This validation shows that the accuracy is higher with the learned edit costs, than with some manually imposed costs or other costs automatically learned by previous methods. Finally we propose an application of the Belief propagation algorithm applied to muscle mechanics.
49
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
50
Tamura, Takeyuki. "Graph Algorithmic Approaches for Structure Inferences in Bioinformatics." 京都大学 (Kyoto University), 2006. http://hdl.handle.net/2433/68893.
Full text