Log in

Relevant bibliographies by topics / Graph / Dissertations / Theses

To see the other types of publications on this topic, follow the link: Graph.

Dissertations / Theses on the topic 'Graph'

Author: Grafiati

Published: 4 June 2021

Last updated: 25 July 2025

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

Select a source type:

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 text

Abstract:

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 verti

APA, Harvard, Vancouver, ISO, and other styles

2

Xu, Jingbo. "GRAPE : parallel graph query engine." Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/28927.

Full text

Abstract:

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 netw

APA, Harvard, Vancouver, ISO, and other styles

3

Hearon, Sean M. "PLANAR GRAPHS, BIPLANAR GRAPHS AND GRAPH THICKNESS." CSUSB ScholarWorks, 2016. https://scholarworks.lib.csusb.edu/etd/427.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

5

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

Full text

Abstract:

Un parcours de graphe est un mécanisme pour visiter de manière itérative les sommets d'un graphe. Cela a été une technique fondamentale dans la conception des algorithmes de graphe depuis les débuts de l'informatique. Bon nombre des premiers parcours étaient basées sur le parcours en largeur(BFS) ou en profondeur (DFS) et cela a donné des algorithmes efficaces pour les problèmes pratiques tels que la distance entre deux sommets, le diamètre, la connectivité, les problèmes de flot et la reconnaissance des graphes planaires. Le but de cette thèse est d'étudier les parcours de graphe Dans cette t

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 con

APA, Harvard, Vancouver, ISO, and other styles

8

Araujo, Julio. "Graph coloring and graph convexity." Nice, 2012. http://www.theses.fr/2012NICE4032.

Full text

Abstract:

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écisi

APA, Harvard, Vancouver, ISO, and other styles

9

Peternek, Fabian Hans Adolf. "Graph compression using graph grammars." Thesis, University of Edinburgh, 2018. http://hdl.handle.net/1842/31094.

Full text

Abstract:

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 severa

APA, Harvard, Vancouver, ISO, and other styles

10

Winerip, Jason. "Graph Linear Complexity." Scholarship @ Claremont, 2008. https://scholarship.claremont.edu/hmc_theses/216.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

<p>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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 inform

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

Thesis(Ph.D.)--Case Western Reserve University, 2010<br>Title 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

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 h

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 o

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 re

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

22

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

Full text

Abstract:

A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs). A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism f

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

24

Irniger, Christophe-André. "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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 c

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

28

Feghali, Carl. "Topics in graph colouring and extremal graph theory." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11790/.

Full text

Abstract:

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 reconfigurat

APA, Harvard, Vancouver, ISO, and other styles

29

Gravier, Sylvain. "Coloration et produits de graphes." Université Joseph Fourier (Grenoble), 1996. http://www.theses.fr/1996GRE10084.

Full text

Abstract:

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, identificat

APA, Harvard, Vancouver, ISO, and other styles

30

Borgwardt, Karsten Michael. "Graph Kernels." Diss., lmu, 2007. http://nbn-resolving.de/urn:nbn:de:bvb:19-71691.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Mehta, Nishali. "Graph Games." The Ohio State University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=osu1275073614.

Full text

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

33

Lin, Matthew. "Graph Cohomology." Scholarship @ Claremont, 2016. https://scholarship.claremont.edu/hmc_theses/82.

Full text

Abstract:

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 synthesiz

APA, Harvard, Vancouver, ISO, and other styles

34

Ragusa, Giorgio. "Graph designs." Doctoral thesis, Università di Catania, 2013. http://hdl.handle.net/10761/1314.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Zighem, Ismail. "Etude d'invariants de graphes planaires." Université Joseph Fourier (Grenoble), 1998. http://www.theses.fr/1998GRE10211.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

36

Le, Ngoc Khang. "Detecting and Coloring some Graph Classes." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN021/document.

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (p. 181-192).<br>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 d

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 que

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

42

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

Full text

Abstract:

Graphs are a very flexible tool within mathematics, as such, numerous problems can be solved by formulating them as an instance of a graph. As a result, however, some of the structures found in real world problems may be lost in a more general graph. An example of this is the 4-Colouring problem which, as a graph problem, is NP-complete. However, when a map is converted into a graph, we observe that this graph has structural properties, namely being (K_5, K_{3,3})-minor-free which can be exploited and as such there exist algorithms which can find 4-colourings of maps in polynomial time. This t

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

45

Yerger, Carl Roger Jr. "Color-critical graphs on surfaces." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37197.

Full text

Abstract:

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 Cha

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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., l

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

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 constan

APA, Harvard, Vancouver, ISO, and other styles

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 text

Abstract:

MinistÃre de l'Enseignement SupÃrieur et de la Recherche<br>Nesta 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

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!