To see the other types of publications on this topic, follow the link: Graph.
Dissertations / Theses on the topic 'Graph'
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.'
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
Ramos, Garrido Lander. "Graph enumeration and random graphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2017. http://hdl.handle.net/10803/405943.
Full textAbstract:
In this thesis we use analytic combinatorics to deal with two related problems: graph enumeration and random graphs from constrained classes of graphs. We are interested in drawing a general picture of some graph families by determining, first, how many elements are there of a given possible size (graph enumeration), and secondly, what is the typical behaviour of an element of fixed size chosen uniformly at random, when the size tends to infinity (random graphs). The problems concern graphs subject to global conditions, such as being planar and/or with restrictions on the degrees of the vertices.
In Chapter 2 we analyse random planar graphs with minimum degree two and three. Using techniques from analytic combinatorics and the concepts of core and kernel of a graph, we obtain precise asymptotic estimates and analyse relevant parameters for random graphs, such as the number of edges or the size of the core, where we obtain Gaussian limit laws. More challenging is the extremal parameter equal to the size of the largest tree attached to the core. In this case we obtain a logarithmic estimate for the expected value together with a concentration result.
In Chapter 3 we study the number of subgraphs isomorphic to a fixed graph in subcritical classes of graphs. We obtain Gaussian limit laws with linear expectation and variance when the fixed graph is 2-connected. The main tool is the analysis of infinite systems of equations by Drmota, Gittenberger and Morgenbesser, using the theory of compact operators. Computing the exact constants for the first estimates of the moments is in general out of reach. For the class of series-parallel graphs we are able to compute them in some particular interesting cases.
In Chapter 4 we enumerate (arbitrary) graphs where the degree of every vertex belongs to a fixed subset of the natural numbers. In this case the associated generating functions are divergent and our analysis uses instead the so-called configuration model. We obtain precise asymptotic estimates for the number of graphs with given number of vertices and edges and subject to the degree restriction. Our results generalize widely previous special cases, such as d-regular graphs or graphs with minimum degree at least d.En aquesta tesi utilitzem l'analítica combinatòria per treballar amb dos problemes relacionats: enumeració de grafs i grafs aleatoris de classes de grafs amb restriccions. En particular ens interessa esbossar un dibuix general de determinades famílies de grafs determinant, en primer lloc, quants grafs hi ha de cada mida possible (enumeració de grafs), i, en segon lloc, quin és el comportament típic d'un element de mida fixa triat a l'atzar uniformement, quan aquesta mida tendeix a infinit (grafs aleatoris). Els problemes en què treballem tracten amb grafs que satisfan condicions globals, com ara ésser planars, o bé tenir restriccions en el grau dels vèrtexs. En el Capítol 2 analitzem grafs planar aleatoris amb grau mínim dos i tres. Mitjançant tècniques de combinatòria analítica i els conceptes de nucli i kernel d'un graf, obtenim estimacions asimptòtiques precises i analitzem paràmetres rellevants de grafs aleatoris, com ara el nombre d'arestes o la mida del nucli, on obtenim lleis límit gaussianes. També treballem amb un paràmetre que suposa un repte més important: el paràmetre extremal que es correspon amb la mida de l'arbre més gran que penja del nucli. En aquest cas obtenim una estimació logarítmica per al seu valor esperat, juntament amb un resultat sobre la seva concentració. En el Capítol 3 estudiem el nombre de subgrafs isomorfs a un graf fix en classes de grafs subcrítiques. Quan el graf fix és biconnex, obtenim lleis límit gaussianes amb esperança i variància lineals. L'eina principal és l'anàlisi de sistemes infinits d'equacions donada per Drmota, Gittenberger i Morgenbesser, que utilitza la teoria d'operadors compactes. El càlcul de les constants exactes de la primera estimació dels moments en general es troba fora del nostre abast. Per a la classe de grafs sèrie-paral·lels podem calcular les constants en alguns casos particulars interessants. En el Capítol 4 enumerem grafs (arbitraris) el grau de cada vèrtex dels quals pertany a un subconjunt fix dels nombres naturals. En aquest cas les funcions generatrius associades són divergents i la nostra anàlisi utilitza l'anomenat model de configuració. El nostre resultat consisteix a obtenir estimacions asimptòtiques precises per al nombre de grafs amb un nombre de vèrtexs i arestes donat, amb la restricció dels graus. Aquest resultat generalitza àmpliament casos particulars existents, com ara grafs d-regulars, o grafs amb grau mínim com a mínim d.
2
Xu, Jingbo. "GRAPE : parallel graph query engine." Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/28927.
Full textAbstract:
The need for graph computations is evident in a multitude of use cases. To support computations on large-scale graphs, several parallel systems have been developed. However, existing graph systems require users to recast algorithms into new models, which makes parallel graph computations as a privilege to experienced users only. Moreover, real world applications often require much more complex graph processing workflows than previously evaluated. In response to these challenges, the thesis presents GRAPE, a distributed graph computation system, shipped with various applications for social network analysis, social media marketing and functional dependencies on graphs. Firstly, the thesis presents the foundation of GRAPE. The principled approach of GRAPE is based on partial evaluation and incremental computation. Sequential graph algorithms can be plugged into GRAPE with minor changes, and get parallelized as a whole. The termination and correctness are guaranteed under a monotonic condition. Secondly, as an application on GRAPE, the thesis proposes graph-pattern association rules (GPARs) for social media marketing. GPARs help users discover regularities between entities in social graphs and identify potential customers by exploring social influence. The thesis studies the problem of discovering top-k diversified GPARs and the problem of identifying potential customers with GPARs. Although both are NP- hard, parallel scalable algorithms on GRAPE are developed, which guarantee a polynomial speedup over sequential algorithms with the increase of processors. Thirdly, the thesis proposes quantified graph patterns (QGPs), an extension of graph patterns by supporting simple counting quantifiers on edges. QGPs naturally express universal and existential quantification, numeric and ratio aggregates, as well as negation. The thesis proves that the matching problem of QGPs remains NP-complete in the absence of negation, and is DP-complete for general QGPs. In addition, the thesis introduces quantified graph association rules defined with QGPs, to identify potential customers in social media marketing. Finally, to address the issue of data consistency, the thesis proposes a class of functional dependencies for graphs, referred to as GFDs. GFDs capture both attribute-value dependencies and topological structures of entities. The satisfiability and implication problems for GFDs are studied and proved to be coNP-complete and NP-complete, respectively. The thesis also proves that the validation problem for GFDs is coNP- complete. The parallel algorithms developed on GRAPE verify that GFDs provide an effective approach to detecting inconsistencies in knowledge and social graphs.
3
Hearon, Sean M. "PLANAR GRAPHS, BIPLANAR GRAPHS AND GRAPH THICKNESS." CSUSB ScholarWorks, 2016. https://scholarworks.lib.csusb.edu/etd/427.
Full textAbstract:
A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.
4
Zuffi, Lorenzo. "Simplicial Complexes From Graphs Toward Graph Persistence." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/13519/.
Full textAbstract:
Persistent homology is a branch of computational topology which uses geometry and topology for shape description and analysis. This dissertation is an introductory study to link persistent homology and graph theory, the connection being represented by various methods to build simplicial complexes from a graph. The methods we consider are the complex of cliques, of independent sets, of neighbours, of enclaveless sets and complexes from acyclic subgraphs, each revealing several properties of the underlying graph. Moreover, we apply the core ideas of persistence theory in the new context of graph theory, we define the persistent block number and the persistent edge-block number.
5
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
6
Myers, Joseph Samuel. "Extremal theory of graph minors and directed graphs." Thesis, University of Cambridge, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.619614.
Full text
7
Henry, Tyson Rombauer. "Interactive graph layout: The exploration of large graphs." Diss., The University of Arizona, 1992. http://hdl.handle.net/10150/185833.
Full textAbstract:
Directed and undirected graphs provide a natural notation for describing many fundamental structures of computer science. Unfortunately graphs are hard to draw in an easy to read fashion. Traditional graph layout algorithms have focused on creating good layouts for the entire graph. This approach works well with smaller graphs, but often cannot produce readable layouts for large graphs. This dissertation presents a novel methodology for viewing large graphs. The basic concept is to allow the user to interactively navigate through large graphs, learning about them in appropriately small and concise pieces. The motivation of this approach is that large graphs contain too much information to be conveyed by a single canonical layout. For a user to be able to understand the data encoded in the graph she must be able to carve up the graph into manageable pieces and then create custom layouts that match her current interests. An architecture is presented that supports graph exploration. It contains three new concepts for supporting interactive graph layout: interactive decomposition of large graphs, end-user specified layout algorithms, and parameterized layout algorithms. The mechanism for creating custom layout algorithms provides the non-programming end-user with the power to create custom layouts that are well suited for the graph at hand. New layout algorithms are created by combining existing algorithms in a hierarchical structure. This method allows the user to create layouts that accurately reflect the current data set and her current interests. In order to explore a large graph, the user must be able to break the graph into small, more manageable pieces. A methodology is presented that allows the user to apply graph traversal algorithms to large graphs to carve out reasonably sized pieces. Graph traversal algorithms can be combined using a visual programming language. This provides the user with the control to select subgraphs that are of particular interest to her. The ability to Parameterize layout algorithms provides the user with control over the layout process. The user can customize the generated layout by changing parameters to the layout algorithm. Layout algorithm parameterization is placed into an interactive framework that allows the user to iteratively fine tune the generated layout. As a proof of concept, examples are drawn from a working prototype that incorporates this methodology.
8
Araujo, Julio. "Graph coloring and graph convexity." Nice, 2012. http://www.theses.fr/2012NICE4032.
Full textAbstract:
Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats figurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons la coloration des graphes qui est l’un des domaines les plus étudiés de théorie des graphes. Nous considérons d’abord trois problèmes de coloration appelés coloration gloutonne, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un problème de décision, appelé bon étiquetage d’arêtes, dont la définition a été motivée par le problème d’affectation de longueurs d’onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d’optimisation des graphes appelé le nombre enveloppe (géodésique). La définition de ce paramètre est motivée par une extension aux graphes des notions d’ensembles et d’enveloppes convexes dans l’espace Euclidien. Enfin, nous présentons dans l’annexe d’autres travaux développés au cours de cette thèse, l’un sur les hypergraphes orientés Eulériens et Hamiltoniens et l’autre concernant les systèmes de stockage distribuésIn this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labelling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems
9
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.
10
Winerip, Jason. "Graph Linear Complexity." Scholarship @ Claremont, 2008. https://scholarship.claremont.edu/hmc_theses/216.
Full textAbstract:
This thesis expands on the notion of linear complexity for a graph as defined by Michael Orrison and David Neel in their paper "The Linear Complexity of a Graph." It considers additional classes of graphs and provides upper bounds for additional types of graphs and graph operations.
11
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
12
Labelle, François. "Graph embeddings and approximate graph coloring." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0031/MQ64386.pdf.
Full text
13
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.
14
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.
15
Ghrab, Amine. "Graph Data Warehousing: Database and Multidimensional Modeling of Graphs." Doctoral thesis, Universite Libre de Bruxelles, 2020. https://dipot.ulb.ac.be/dspace/bitstream/2013/313535/3/ToC.pdf.
Full textAbstract:
Over the last decade, we have witnessed the emergence of networks in a wide spectrum of application domains, ranging from social and information networks to biological and transportation networks.Graphs provide a solid theoretical foundation for modeling complex networks and revealing valuable insights from both the network structure and the data embedded within its entities.As the business and social environments are getting increasingly complex and interconnected, graphs became a widespread abstraction at the core of the information infrastructure supporting those environments. Modern information systems consist of a large number of sophisticated and interacting business entities that naturally form graphs. In particular, integrating graphs into data warehouse systems received a lot of interest from both academia and industry. Indeed, data warehouses are the central enterprise's information repository and are critical for proper decision support and future planning. Graph warehousing is emerging as the field that extends current information systems with graph management and analytics capabilities. Many approaches were proposed to address the graph data warehousing challenge. These efforts laid the foundation for multidimensional modeling and analysis of graphs. However, most of the proposed approaches partially tackle the graph warehousing problem by being restricted to simple abstractions such as homogeneous graphs or ignoring important topics such as multidimensional integrity constraints and dimension hierarchies.In this dissertation, we conduct a systematic study of the graph data warehousing topic and address the key challenges of database and multidimensional modeling of graphs.We first propose GRAD, a new graph database model tailored for graph warehousing and OLAP analytics. GRAD aims to provide analysts with a set of simple, well-defined, and adaptable conceptual components to support rich semantics and perform complex analysis on graphs.Then, we define the multidimensional concepts for heterogeneous attributed graphs and highlight the new types of measures that could be derived. We project this multidimensional model on property graphs and explore how to extract the candidate multidimensional concepts and build graph cubes. Then, we extend the multidimensional model by integrating GRAD and show how GRAD facilitates multidimensional graph modeling, and enables supporting dimension hierarchies and building new types of OLAP cubes on graphs.Afterward, we present TopoGraph, a graph data warehousing framework that extends current graph warehousing models with new types of cubes and queries combining graph-oriented and OLAP querying. TopoGraph goes beyond traditional OLAP cubes, which process value-based grouping of tables, by considering also the topological properties of the graph elements. And it goes beyond current graph warehousing models by proposing new types of graph cubes. These cubes embed a rich repertoire of measures that could be represented with numerical values, with entire graphs, or as a combination of them.Finally, we propose an architecture of the graph data warehouse and describe its main building blocks and the remaining gaps. The various components of the graph warehousing framework can be effectively leveraged as a foundation for designing and building industry-grade graph data warehouses.We believe that our research in this thesis brings us a step closer towards a better understanding of graph warehousing. Yet, the models and framework we proposed are the tip of the iceberg. The marriage of graph and warehousing technologies will bring many exciting research opportunities, which we briefly discuss at the end of the thesis.Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished
16
Zhang, Shijie. "Index-based Graph Querying and Matching in Large Graphs." Cleveland, Ohio : Case Western Reserve University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=case1263256028.
Full textAbstract:
Thesis(Ph.D.)--Case Western Reserve University, 2010Title from PDF (viewed on 2010-04-12) Department of Electrical Engineering and Computer Science (EECS) Includes abstract Includes bibliographical references and appendices Available online via the OhioLINK ETD Center
17
Busatto, Giorgio. "An abstract model of hierarchical graphs and hierarchical graph transformation." Oldenburg : Univ., Fachbereich Informatik, 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=967851955.
Full text
18
Ferguson, David G. "Topics in graph colouring and graph structures." Thesis, London School of Economics and Political Science (University of London), 2013. http://etheses.lse.ac.uk/735/.
Full textAbstract:
This thesis investigates problems in a number of different areas of graph theory. These problems are related in the sense that they mostly concern the colouring or structure of the underlying graph. The first problem we consider is in Ramsey Theory, a branch of graph theory stemming from the eponymous theorem which, in its simplest form, states that any sufficiently large graph will contain a clique or anti-clique of a specified size. The problem of finding the minimum size of underlying graph which will guarantee such a clique or anti-clique is an interesting problem in its own right, which has received much interest over the last eighty years but which is notoriously intractable. We consider a generalisation of this problem. Rather than edges being present or not present in the underlying graph, each is assigned one of three possible colours and, rather than considering cliques, we consider cycles. Combining regularity and stability methods, we prove an exact result for a triple of long cycles. We then move on to consider removal lemmas. The classic Removal Lemma states that, for n sufficiently large, any graph on n vertices containing o(n^3) triangles can be made triangle-free by the removal of o(n^2) edges. Utilising a coloured hypergraph generalisation of this result, we prove removal lemmas for two classes of multinomials. Next, we consider a problem in fractional colouring. Since finding the chromatic number of a given graph can be viewed as an integer programming problem, it is natural to consider the solution to the corresponding linear programming problem. The solution to this LP-relaxation is called the fractional chromatic number. By a probabilistic method, we improve on the best previously known bound for the fractional chromatic number of a triangle-free graph with maximum degree at most three. Finally, we prove a weak version of Vizing's Theorem for hypergraphs. We prove that, if H is an intersecting 3-uniform hypergraph with maximum degree D and maximum multiplicity m, then H has at most 2D+m edges. Furthermore, we prove that the unique structure achieving this maximum is m copies of the Fano Plane.
19
Sandström, Emil. "Molecular Optimization Using Graph-to-Graph Translation." Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-172584.
Full textAbstract:
Drug development is a protracted and expensive process. One of the main challenges indrug discovery is to find molecules with desirable properties. Molecular optimization is thetask of optimizing precursor molecules by affording them with desirable properties. Recentadvancement in Artificial Intelligence, has led to deep learning models designed for molecularoptimization. These models, that generates new molecules with desirable properties, have thepotential to accelerate the drug discovery. In this thesis, I evaluate the current state-of-the-art graph-to-graph translation model formolecular optimization, the HierG2G. I examine the HierG2G’s performance using three testcases, where the second test is designed, with the help of chemical experts, to represent a commonmolecular optimization task. The third test case, tests the HierG2G’s performance on,for the model, previously unseen molecules. I conclude that, in each of the test cases, the HierG2Gcan successfully generate structurally similar molecules with desirable properties givena source molecule and an user-specified desired property change. Further, I benchmark the HierG2Gagainst two famous string-based models, the seq2seq and the Transformer. My resultsuggests that the seq2seq is the overall best model for molecular optimization, but due to thevarying performance among the models, I encourage a potential user to simultaneously use allthree models for molecular optimization.
20
Zwolak, Michal. "Streaming Graph Partitioning with Graph Convolutional Networks." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-280320.
Full textAbstract:
In this work, we present a novel approach to the streaming graph partitioning problem which handles unbounded streams.Graph partitioning is a process of dividing a graph into groups of nodes or edges. Traditional, offline partitioning methods require a priori access to the entire graph and make multiple passes over the data in order to compute partitions. However, recently the demand for real-time analysis of graph data sparked the prospect of online partitioning. In such an approach, the graph arrives as a stream of nodes or edges which are assigned to partitions as they come and are never reassigned again. Additionally, in the case of modern systems, where graphs constantly grow, the streams are unbounded. The main goals of graph partitioning are preserving data locality, so related items belong to the same partitions, and load balance, so partitions have similar sizes.State-of-the-art streaming graph partitioning algorithms fulfil the two latter requirements. However, they make their partitioning decisions based on internal state, which grows as new items arrive. Thus, they are not capable of processing unbounded streams. At some point, the state will exceed the memory capacity of the machine the algorithm is running on. Moreover, modern stream data processors run in a distributed environment. In such a setting synchronisation of a shared state is an expensive operation.In the proposed approach, in addition to structural information about the graph, we utilise attributes associated with vertices such as user’s location, age, or previous actions. In order to do that, we employ a graph convolutional network (GCN), which is a novel method of graph representation learning. A GCN can embed both structural and feature-based characteristics of each vertex into a low-dimensional space. Secondly, we feed these representations into a neural network, which assigns incoming items to partitions. Such a method requires only the networks’ parameters’ values in order to make a partitioning decision. Thus, the size of the state remains constant regardless of the length of the stream.We present both unsupervised and supervised approaches to train the proposed framework. Moreover, we describe a method to apply the models to partition the streaming graph. We evaluate the performance of our novel method on three real-world graph datasets and compare it with the state-of-the-art HDRF algorithm as well as a simple, stateless hash-based approach. The experimental results show the generalisation capabilities of our models. Moreover, our methods can yield up to 16% lower replication factor than hash partitioning which corresponds to only 1% increase compared to HDRF. At thesame time, we reduce state requirements from linear to constant, which for the graph with 230k vertices and 5.7M edges translates to 125 times smaller size of the state and allows for processing unbounded streams. Nevertheless, the latency of our methods is about 20 times higher than HDRF.I det här arbetet presenterar vi en ny metod för grafpartitionering av obundna strömmar.Grafpartitionering är en process att dela upp en graf i grupper av noder eller kanter. Traditionella, offline-partitioneringsmetoder kräver en priori åtkomst till hela grafen och gör flera passeringar över datan för att beräkna partitioner. Nyligen gjorde dock efterfrågan på realtidsanalys av grafdata möjligheterna att partitionera online. I ett sådant tillvägagångssätt ankommer grafen som en ström av noder eller kanter som tilldelas partitioner när de kommer och aldrig tilldelas igen. Dessutom, för moderna system, där grafer ständigt växer, är strömmarna obegränsade. Huvudmålen för grafpartitionering är att bevara datalokalitet, så relaterade objekt tillhör samma partitioner och lastbalans, så partitioner har liknande storlekar.Avancerade algoritmer för strömmande grafpartitionering uppfyller de två senare kraven. De fattar emellertid sina partitionsbeslut baserade på internt tillstånd, som växer när nya artiklar kommer. Således kan de inte bearbeta obundna strömmar. Vid någon tidpunkt kommer tillståndet att överskrida minneskapaciteten för maskinen som algoritmen kör på. Dessutom körs moderna databehandlare i en distribuerad miljö. I en sådan inställning är synkronisering av ett delat tillstånd en dyr operation.I det föreslagna tillvägagångssättet använder vi, utöver strukturell information om grafen, attribut som är förknippade med hörn som användarens plats, ålder eller tidigare åtgärder. För att göra det använder vi ett grafkonvolutional nätverk (GCN), som är en ny metod för grafrepresentation. En GCN kan bädda in både strukturella och funktionsbaserade egenskaper hos varje toppunkt i ett lågdimensionellt utrymme. För det andra matar vi dessa representationer i ett neuralt nätverk, som tilldelar inkommande objekt till partitioner. En sådan metod kräver bara nätverksparametrarnas värden för att fatta ett partitionsbeslut. Således förblir tillståndets storlek konstant oavsett strömmens längd.Vi presenterar både obevakade och övervakade tillvägagångssätt för att utbilda det föreslagna ramverket. Dessutom beskriver vi en metod för att tillämpa modellerna för att partitionera strömningsgrafen. Vi utvärderar prestandan för vår nya metod på tre grafiska datauppsättningar i verkligheten och jämför den med den senaste HDRF-algoritmen samt en enkel, statslös hashbaserad strategi. De experimentella resultaten visar generaliseringsförmågan hos våra modeller. Dessutom kan våra metoder ge upp till 16% lägre replikationsfaktor än hashpartitionering, vilket motsvarar endast 1% ökning jämfört med HDRF. Samtidigt minskar vi tillståndskraven från linjär till konstant,vilket för diagrammet med 230k vertikaler och 5,7M kanter motsvarar 125 gånger mindre storlek på tillståndet. Trots det är latens för våra metoder ungefär 20 gånger högre än HDRF.
21
Medrano, Archie T. "Super-Euclidean graphs and super-Heisenberg graphs : their spectral and graph-theoretic properties /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 1998. http://wwwlib.umi.com/cr/ucsd/fullcit?p9901440.
Full text
22
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
23
Seierstad, Taral Guldahl. "The phase transition in random graphs and random graph processes." Doctoral thesis, [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=985760044.
Full text
24
Irniger, Christophe-André. "Graph matching filtering databases of graphs using machine learning techniques." Berlin Aka, 2005. http://deposit.ddb.de/cgi-bin/dokserv?id=2677754&prov=M&dok_var=1&dok_ext=htm.
Full text
25
Crinion, Tim. "Chamber graphs of some geometries related to the Petersen graph." Thesis, University of Manchester, 2013. https://www.research.manchester.ac.uk/portal/en/theses/chamber-graphs-of-some-geometries-related-to-the-petersen-graph(f481f0af-7c39-4728-8928-571495d1217a).html.
Full textAbstract:
In this thesis we study the chamber graphs of the geometries ΓpA2nΓ1q, Γp3A7q, ΓpL2p11qq and ΓpL2p25qq which are related to the Petersen graph [4, 13]. In Chapter 2 we look at the chamber graph of ΓpA2nΓ1q and see what minimal paths between chambers look like. Chapter 3 finds and proves the diameter of these chamber graphs and we see what two chambers might look like if they are as far apart as possible. We discover the full automorphism group of the chamber graph. Chapters 4, 5 and 6 focus on the chamber graphs of ΓpL2p11qq,ΓpL2p25qq and Γp3A7q respectively. We ask questions such as what two chambers look like if they are as far apart as possible, and we find the automorphism groups of the chamber graphs.
26
Deering, Jessie. "Uphill & Downhill Domination in Graphs and Related Graph Parameters." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/honors/103.
Full textAbstract:
Placing degree constraints on the vertices of a path allows the definitions of uphill and downhill paths. Specifically, we say that a path π = v1, v2,...vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1). Conversely, a path π = u1, u2,...uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(ui) ≤ deg(ui+1). We investigate graphical parameters related to downhill and uphill paths in graphs. For example, a downhill path set is a set P of vertex disjoint downhill paths such that every vertex v ∈ V belongs to at least one path in P, and the downhill path number is the minimum cardinality of a downhill path set of G. For another example, the downhill domination number of a graph G is defined to be the minimum cardinality of a set S of vertices such that every vertex in V lies on a downhill path from some vertex in S. The uphill domination number is defined as expected. We determine relationships among these invariants and other graphical parameters related to downhill and uphill paths. We also give a polynomial time algorithm to find a minimum downhill dominating set and a minimum uphill dominating set for any graph.
27
Reed, Bruce. "A semi-strong perfect graph theorem /." Thesis, McGill University, 1986. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=72812.
Full text
28
Gravier, Sylvain. "Coloration et produits de graphes." Université Joseph Fourier (Grenoble), 1996. http://www.theses.fr/1996GRE10084.
Full textAbstract:
Dans la première partie, nous étudions la notion de coloration par listes. Un graphe d'ordre n est k-liste colorable si, quelque soit la donnée de n listes de taille k (une par sommet), il est possible d'attribuer, à chaque sommet, une couleur de sa liste, de sorte que deux sommets voisins quelconques aient des couleurs différentes. Nous donnons un rappel des différents résultats classiques sur la coloration par liste. Nous abordons l'aspect de la complexité du problème de liste-coloration. Après une étude des différentes constructions utilisées en théorie des graphes (contraction, identification,…), nous donnons un théorème de type Hajós pour la coloration par listes. Enfin, nous terminons cette étude en abordant la conjecture de Vizing par un angle d'attaque nouveau, ce qui nous permet d'obtenir des résultats sur la classe des graphes sans griffe. Dans un second temps, nous traitons l'aspect algorithmique de la coloration, en donnant un algorithme «séquentiel» d'échange chromatique qui nous permet de colorer et de reconnaître deux nouvelles classes de graphes parfaits. Finalement, nous étudions le comportement de certains invariants de graphes via certains produits. Le nombre d'absorpion du produit croisé d'une chaîne et d'une antichaîne est donné, ainsi que certaines valeurs du produit croisé de deux chaînes. Nous proporons une nouvelle approche de la conjecture de Hedetniemi, en étudiant le problème du nombre chromatique du produit fibré (sous-produit du produit croisé). Nous terminons cette étude sur les prdouits, en abordant deux problèmes classiques de recouvrement, l'hamiltonicité et le plongement d'arbres dans l'hypercube. Nous donnons une conditions nécessaire et suffisante pour que le produit croisé de deux graphes hamiltoniens soit hamiltonien. Nous définissons une large classe d'arbres couvrants l'hypercube, et donnons une partition des arêtes de l'hypercube en de tels arbres
29
Feghali, Carl. "Topics in graph colouring and extremal graph theory." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11790/.
Full textAbstract:
In this thesis we consider three problems related to colourings of graphs and one problem in extremal graph theory. Let $G$ be a connected graph with $n$ vertices and maximum degree $\Delta(G)$. Let $R_k(G)$ denote the graph with vertex set all proper $k$-colourings of $G$ and two $k$-colourings are joined by an edge if they differ on the colour of exactly one vertex. Our first main result states that $R_{\Delta(G)+1}(G)$ has a unique non-trivial component with diameter $O(n^2)$. This result can be viewed as a reconfigurations analogue of Brooks' Theorem and completes the study of reconfigurations of colourings of graphs with bounded maximum degree. A Kempe change is the operation of swapping some colours $a$, $b$ of a component of the subgraph induced by vertices with colour $a$ or $b$. Two colourings are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. Our second main result states that all $\Delta(G)$-colourings of a graph $G$ are Kempe equivalent unless $G$ is the complete graph or the triangular prism. This settles a conjecture of Mohar (2007). Motivated by finding an algorithmic version of a structure theorem for bull-free graphs due to Chudnovsky (2012), we consider the computational complexity of deciding if the vertices of a graph can be partitioned into two parts such that one part is triangle-free and the other part is a collection of complete graphs. We show that this problem is NP-complete when restricted to five classes of graphs (including bull-free graphs) while polynomial-time solvable for the class of cographs. Finally we consider a graph-theoretic version formulated by Holroyd, Spencer and Talbot (2007) of the famous Erd\H{o}s-Ko-Rado Theorem in extremal combinatorics and obtain some results for the class of trees.
30
Borgwardt, Karsten Michael. "Graph Kernels." Diss., lmu, 2007. http://nbn-resolving.de/urn:nbn:de:bvb:19-71691.
Full text
31
Mehta, Nishali. "Graph Games." The Ohio State University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=osu1275073614.
Full text
32
Martin, Jeremy Leander. "Graph varieties /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2002. http://wwwlib.umi.com/cr/ucsd/fullcit?p3061650.
Full text
33
Lin, Matthew. "Graph Cohomology." Scholarship @ Claremont, 2016. https://scholarship.claremont.edu/hmc_theses/82.
Full textAbstract:
What is the cohomology of a graph? Cohomology is a topological invariant and encodes such information as genus and euler characteristic. Graphs are combinatorial objects which may not a priori admit a natural and isomorphism invariant cohomology ring. In this project, given any finite graph G, we constructively define a cohomology ring H*(G) of G. Our method uses graph associahedra and toric varieties. Given a graph, there is a canonically associated convex polytope, called the graph associahedron, constructed from G. In turn, a convex polytope uniquely determines a toric variety. We synthesize these results, and describe the cohomology of the associated variety directly in terms of the graph G itself.
34
Ragusa, Giorgio. "Graph designs." Doctoral thesis, Università di Catania, 2013. http://hdl.handle.net/10761/1314.
Full text
35
Zighem, Ismail. "Etude d'invariants de graphes planaires." Université Joseph Fourier (Grenoble), 1998. http://www.theses.fr/1998GRE10211.
Full textAbstract:
Dans la première partie, nous construisons, à partir de relations linéaires de récurrence, des invariants de graphes planaires 4-réguliers prenant leurs valeurs dans un anneau commutatif. Ces relations représentent des règles récursives bien définies sur cette catégories de graphes, ramenant le calcul des valeurs de l'invariant en ces graphes à une combinaison linéaire d'autres graphes plus réduits. Après avoir dégagé quelques conditions nécessaires pour que ces règles soient mutuellement compatibles, nous montrons en utilisant un résultat de la théorie des systèmes de réécriture qu'elles sont aussi suffisantes. Nous terminons cette partie en évoquant la relation avec le polynôme de Kauffman et en montrant que, pour une évaluation particulière de ses variables, ce polynôme peut être défini à partir de notre invariant. Ce qui constitue une nouvelle preuve d'existence de ce polynôme. La seconde partie aborde le problème de la détermination du nombre d'absorption des graphes de type grille. Dans un premier temps, nous déterminons ce nombre pour les petites grilles croisées (graphes produit croisé de deux chaînes de longueurs k et n, avec k ≤ 33 et n ≤ 40). En utilisant la programmation dynamique, nous présentons pour k fixé un algorithme linéaire en n pour calculer ce nombre. On en déduit alors que ce nombre vérifie des formules simples en fonction de k et n. Ensuite, nous montrons par récurrence, en prenant ces valeurs comme base de récurrence, que ces formules sont vérifiées par ce nombre, pour tous k = 12 ou k ≥ 14 et n ≥ k. Finalement, nous donnons quelques bornes du nombre d'absorption de la grille carrée (graphe produit carré de deux chaînes) qui améliorent les résultats déjà connus
36
Le, Ngoc Khang. "Detecting and Coloring some Graph Classes." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN021/document.
Full textAbstract:
Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interditsGraphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ -bounding function for this class and show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs
37
Weinstein, Lee. "Empirical study of graph properties with particular interest towards random graphs." Diss., Connect to the thesis, 2005. http://hdl.handle.net/10066/1485.
Full text
38
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.
39
Riordan, Oliver Maxim. "Subgraphs of the discrete torus, random graphs and general graph invariants." Thesis, University of Cambridge, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.624757.
Full text
40
Evertsson, Simon. "Accelerating graph isomorphismqueries in a graph database usingthe GPU." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-310380.
Full textAbstract:
Over the last decade the popularity of utilizing the parallel nature of thegraphical processing unit in general purpose problems has grown a lot. TodayGPUs are used in many different fields where one of them is the accelerationof database systems. Graph databases are a kind of database systems that havegained popularity in recent years. Such databases excel especially for datawhich is highly interconnected. Querying a graph database often requiresfinding subgraphs which structurally matches a query graph, i.e. isomorphicsubgraphs. In this thesis a method for performing subgraph isomorphism queriesnamed GPUGDA is proposed, extending previous work of GPU-accelerating subgraphisomorphism queries. The query performance of GPUGDA was evaluated andcompared to the performance of storing the same graph in Neo4j and makingqueries in Cypher, the query language of Neo4j. The results show largespeedups of up to 470x when the query graph is dense whilst performingslightly worse than Neo4j for sparse query graphs in larger databases.
41
Jin, Wei. "GRAPH PATTERN MATCHING, APPROXIMATE MATCHING AND DYNAMIC GRAPH INDEXING." Case Western Reserve University School of Graduate Studies / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=case1307547974.
Full text
42
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.
43
Alzaidi, Esraa Raheem. "EXPERIMENTS ON CHORDAL GRAPH HELLIFICATION." Kent State University / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1494430064980414.
Full text
44
Meek, Darrin Leigh. "On graph approximation heuristics : an application to vertex cover on planar graphs." Thesis, Georgia Institute of Technology, 1991. http://hdl.handle.net/1853/24088.
Full text
45
Yerger, Carl Roger Jr. "Color-critical graphs on surfaces." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37197.
Full textAbstract:
A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring, c, of C, can be extended inside the cycle, or there exists a subgraph H with at most a number of vertices exponential in q such that c can not be extended to a 5-coloring of H. In Chapter 2, we proved an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. In Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface S, with Euler genus g and has no cycles of length four through ten, then G has at most 2442g + 37 vertices.
46
Ahmed, Algabli Shaima. "Learning the Graph Edit Distance through embedding the graph matching." Doctoral thesis, Universitat Rovira i Virgili, 2020. http://hdl.handle.net/10803/669612.
Full textAbstract:
Els gràfics són estructures de dades abstractes que s’utilitzen per modelar problemes reals amb dues entitats bàsiques: nodes i vores. Cada
node o vèrtex representa un punt d'interès rellevant d'un problema i cada vora representa la relació entre aquests punts. Es poden atribuir
nodes i vores per augmentar la precisió del model, cosa que significa que aquests atributs podrien variar des de vectors de característiques fins
a etiquetes de descripció. A causa d'aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per ordinador, la biomèdica i
l'anàlisi de xarxa, etc., la primera part d'aquesta tesi presenta un mètode general per aprendre automàticament els costos d'edició que
comporta l'edició de gràfics. Distància. El mètode es basa en incrustar parells de gràfics i el seu mapeig de node a node de veritat terrestre en un
espai euclidià. D’aquesta manera, l’algoritme d’aprenentatge no necessita calcular cap concordança de gràfics tolerant als errors, que és
l’inconvenient principal d’altres mètodes a causa de la seva intrínseca complexitat computacional exponencial. No obstant això, el mètode
d’aprenentatge té la principal restricció que els costos d’edició han de ser constants. A continuació, posem a prova aquest mètode amb diverses
bases de dades gràfiques i també l’aplicem per realitzar el registre d’imatges. A la segona part de la tesi, aquest mètode es particularitza a la
verificació d’empremtes dactilars. Les dues diferències principals respecte a l’altre mètode són que només definim els costos d’edició de
substitució als nodes. Per tant, suposem que els gràfics no tenen arestes. I també, el mètode d’aprenentatge no es basa en una classificació
lineal sinó en una regressió lineal.Los gráficos son estructuras de datos abstractas 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 borde representa la relación entre estos puntos. Se podrían atribuir nodos y bordes para aumentar la precisión del modelo, lo que significa que estos atributos podrían variar de vectores de características a etiquetas de descripción. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como visión por computadora, biomédicos y análisis de redes, etc. La primera parte de esta tesis presenta un método general para aprender automáticamente los costos de edición involucrados en la Edición de Gráficos Distancia. El método se basa en incrustar pares de gráficos y su mapeo de nodo a nodo de verdad fundamental en un espacio euclidiano. De esta manera, el algoritmo de aprendizaje no necesita calcular ninguna coincidencia de gráfico tolerante a errores, que es el principal inconveniente de otros métodos debido a su complejidad computacional exponencial intrínseca. Sin embargo, el método de aprendizaje tiene la principal restricción de que los costos de edición deben ser constantes. Luego probamos este método con varias bases de datos de gráficos y también lo aplicamos para realizar el registro de imágenes. En la segunda parte de la tesis, este método se especializa en la verificación de huellas digitales. Las dos diferencias principales con respecto al otro método son que solo definimos los costos de edición de sustitución en los nodos. Por lo tanto, suponemos que los gráficos no tienen aristas. Y también, el método de aprendizaje no se basa en una clasificación lineal sino en una regresión lineal.
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 model, 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, biomedics, and network analysis, and so on .The first part of this thesis presents a general method to automatically learn the edit costs involved in the Graph Edit Distance. The method is based on embedding pairs of graphs and their ground-truth node-tonode mapping into a Euclidean space. In this way, the learning algorithm does not need to compute any Error-Tolerant Graph Matching, which is the main drawback of other methods due to its intrinsic exponential computational complexity. Nevertheless, the learning method has the main restriction that edit costs have to be constant. Then we test this method with several graph databases and also we apply it to perform image registration. In the second part of the thesis, this method is particularized to fingerprint verification. The two main differences with respect to the other method are that we only define the substitution edit costs on the nodes. Thus, we assume graphs do not have edges. And also, the learning method is not based on a linear classification but on a linear regression.
47
Normann, Per. "Parallel graph coloring : Parallel graph coloring on multi-core CPUs." Thesis, Uppsala universitet, Avdelningen för beräkningsvetenskap, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-227656.
Full textAbstract:
In recent times an evident trend in hardware is to opt for multi-core CPUs. This has lead to a situation where an increasing number of sequential algorithms are parallelized to fit these new multi-core environments. The greedy Multi-Coloring algorithm is a strictly sequential algorithm that is used in a wide range of applications. The application in focus is on decomposition by graph coloring for preconditioning techniques suitable for iterative solvers like the and methods. In order to perform all phases of these iterative solvers in parallel the graph analysis phase needs to be parallelized. Albeit many attempts have been made to parallelize graph coloring non of these attempts have successfully put the greedy Multi-Coloring algorithm into obsolescence. In this work techniques for parallel graph coloring are proposed and studied. Quantitative results, which represent the number of colors, confirm that the best new algorithm, the Normann algorithm, is performing on the same level as the greedy Multi-Coloring algorithm. Furthermore, in multi-core environments the parallel Normann algorithm fully outperforms the classical greedy Multi-Coloring algorithm for all large test matrices. With the features of the Normann algorithm quantified and presented in this work it is now possible to perform all phases of iterative solvers like and methods in parallel.
48
Sarkar, Medha Shukla. "GXL, a graph transformation language with scoping and graph parameters." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0013/NQ52862.pdf.
Full text
49
Wu, Yinghui. "Extending graph homomorphism and simulation for real life graph matching." Thesis, University of Edinburgh, 2011. http://hdl.handle.net/1842/5022.
Full textAbstract:
Among the vital problems in a variety of emerging applications is the graph matching problem, which is to determine whether two graphs are similar, and if so, find all the valid matches in one graph for the other, based on specified metrics. Traditional graph matching approaches are mostly based on graph homomorphism and isomorphism, falling short of capturing both structural and semantic similarity in real life applications. Moreover, it is preferable while difficult to find all matches with high accuracy over complex graphs. Worse still, the graph structures in real life applications constantly bear modifications. In response to these challenges, this thesis presents a series of approaches for ef?ciently solving graph matching problems, over both static and dynamic real life graphs. Firstly, the thesis extends graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the semantic similarity of nodes. The graph similarity is then measured by the metrics based on these extensions. Several optimization problems for graph matching based on the new metrics are studied, with approximation algorithms having provable guarantees on match quality developed. Secondly, although being extended in the above work, graph matching is defined in terms of functions, which cannot capture more meaningful matches and is usually hard to compute. In response to this, the thesis proposes a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, the thesis defines graph pattern matching based on a notion of bounded simulation relation, an extension of graph simulation. With this revision, graph pattern matching is in cubic-time by providing such an algorithm, rather than intractable. Thirdly, real life graphs often bear multiple edge types. In response to this, the thesis further extends and generalizes the proposed revisions of graph simulation to a more powerful case: a novel set of reachability queries and graph pattern queries, constrained by a subclass of regular path expressions. Several fundamental problems of the queries are studied: containment, equivalence and minimization. The enriched reachability query does not increase the complexity of the above problems, shown by the corresponding algorithms. Moreover, graph pattern queries can be evaluated in cubic time, where two such algorithms are proposed. Finally, real life graphs are frequently updated with small changes. The thesis investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. Besides studying the results on the complexity bounds, the thesis provides the experimental study verifying that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.
50
AraÃjo, JÃlio CÃsar Silva. "Graph coloring and graph convexity / ColoraÃÃo em convexidade em grafos." Universidade Federal do CearÃ, 2012. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=8346.
Full textAbstract:
MinistÃre de l'Enseignement SupÃrieur et de la RechercheNesta tese, estudamos vÃrios problemas de teoria dos grafos relativos à coloraÃÃo e convexidade em grafos. A maioria dos resultados contidos aqui sÃo ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloraÃÃo de grafos que à uma das Ãreas mais importantes de teoria dos grafos. Primeiro, consideramos trÃs problemas de coloraÃÃo chamados coloraÃÃo gulosa, coloraÃÃo ponderada e coloraÃÃo ponderada imprÃpria. Em seguida, discutimos um problema de decisÃo, chamado boa rotulagem de arestas, cuja definiÃÃo foi motivada pelo problema de atribuiÃÃo de frequÃncias em redes Ãticas. A segunda parte desta tese à dedicada a um parÃmetro de otimizaÃÃo em grafos chamado de nÃmero de fecho (geodÃtico). A definiÃÃo deste parÃmetro à motivada pela extensÃo das noÃÃes de conjuntos e fecho convexos no espaÃo Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuÃdo.
In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems.