To see the other types of publications on this topic, follow the link: Application of graph theory.
Dissertations / Theses on the topic 'Application of graph theory'
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 'Application of graph theory.'
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
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
2
Eggemann, Nicole. "Some applications of graph theory." Thesis, Brunel University, 2009. http://bura.brunel.ac.uk/handle/2438/3953.
Full text
3
Ferrer, Sumsi Miquel. "Theory and Algorithms on the Median Graph. Application to Graph-based Classification and Clustering." Doctoral thesis, Universitat Autònoma de Barcelona, 2008. http://hdl.handle.net/10803/5788.
Full textAbstract:
Donat un conjunt d'objectes, el concepte genèric de mediana està definit com l'objecte amb la suma de distàncies a tot el conjunt, més petita. Sovint, aquest concepte és usat per a obtenir el representant del conjunt. En el reconeixement estructural de patrons, els grafs han estat usats normalment per a representar objectes complexos. En el domini dels grafs, el concepte de mediana és conegut com median graph. Potencialment, té les mateixes aplicacions que el concepte de mediana per poder ser usat com a representant d'un conjunt de grafs.
Tot i la seva simple definició i les potencials aplicacions, s'ha demostrat que el seu càlcul és una tasca extremadament complexa. Tots els algorismes existents només han estat capaços de treballar amb conjunts petits de grafs, i per tant, la seva aplicació ha estat limitada en molts casos a usar dades sintètiques sense significat real. Així, tot i el seu potencial, ha restat com un concepte eminentment teòric.
L'objectiu principal d'aquesta tesi doctoral és el d'investigar a fons la teoria i l'algorísmica relacionada amb el concepte de medinan graph, amb l'objectiu final d'extendre la seva aplicabilitat i lliurar tot el seu potencial al món de les aplicacions reals. Per això, presentem nous resultats teòrics i també nous algorismes per al seu càlcul. Des d'un punt de vista teòric aquesta tesi fa dues aportacions fonamentals. Per una banda, s'introdueix el nou concepte d'spectral median graph. Per altra banda es mostra que certes de les propietats teòriques del median graph poden ser millorades sota determinades condicions. Més enllà de les aportacioncs teòriques, proposem cinc noves alternatives per al seu càlcul. La primera d'elles és una conseqüència directa del concepte d'spectral median graph. Després, basats en les millores de les propietats teòriques, presentem dues alternatives més per a la seva obtenció. Finalment, s'introdueix una nova tècnica per al càlcul del median basat en el mapeig de grafs en espais de vectors, i es proposen dos nous algorismes més.
L'avaluació experimental dels mètodes proposats utilitzant una base de dades semi-artificial (símbols gràfics) i dues amb dades reals (mollècules i pàgines web), mostra que aquests mètodes són molt més eficients que els existents. A més, per primera vegada, hem demostrat que el median graph pot ser un bon representant d'un conjunt d'objectes utilitzant grans quantitats de dades. Hem dut a terme experiments de classificació i clustering que validen aquesta hipòtesi i permeten preveure una pròspera aplicació del median graph a un bon nombre d'algorismes d'aprenentatge.
Given a set of objects, the generic concept of median is defined as the object with the smallest sum of distances to all the objects in the set. It has been often used as a good alternative to obtain a representative of the set.
In structural pattern recognition, graphs are normally used to represent structured objects. In the graph domain, the concept analogous to the median is known as the median graph. By extension, it has the same potential applications as the generic median in order to be used as the representative of a set of graphs.
Despite its simple definition and potential applications, its computation has been shown as an extremely complex task. All the existing algorithms can only deal with small sets of graphs, and its application has been constrained in most cases to the use of synthetic data with no real meaning. Thus, it has mainly remained in the box of the theoretical concepts.
The main objective of this work is to further investigate both the theory and the algorithmic underlying the concept of the median graph with the final objective to extend its applicability and bring all its potential to the world of real applications. To this end, new theory and new algorithms for its computation are reported. From a theoretical point of view, this thesis makes two main contributions. On one hand, the new concept of spectral median graph. On the other hand, we show that some of the existing theoretical properties of the median graph can be improved under some specific conditions. In addition to these theoretical contributions, we propose five new ways to compute the median graph. One of them is a direct consequence of the spectral median graph concept. In addition, we provide two new algorithms based on the new theoretical properties. Finally, we present a novel technique for the median graph computation based on graph embedding into vector spaces. With this technique two more new algorithms are presented.
The experimental evaluation of the proposed methods on one semi-artificial and two real-world datasets, representing graphical symbols, molecules and webpages, shows that these methods are much more ecient than the existing ones. In addition, we have been able to proof for the first time that the median graph can be a good representative of a class in large datasets. We have performed some classification and clustering experiments that validate this hypothesis and permit to foresee a successful application of the median graph to a variety of machine learning algorithms.
4
Pappone, Francesco. "Graph neural networks: theory and applications." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/23893/.
Full textAbstract:
Le reti neurali artificiali hanno visto, negli ultimi anni, una crescita vertiginosa nelle loro applicazioni e nelle architetture dei modelli impiegati. In questa tesi introduciamo le reti neurali su domini euclidei, in particolare mostrando l’importanza dell’equivarianza di traslazione nelle reti convoluzionali, e introduciamo, per analogia, un’estensione della convoluzione a dati strutturati come grafi. Inoltre presentiamo le architetture dei principali Graph Neural Network ed esponiamo, per ognuna delle tre architetture proposte (Spectral graph Convolutional Network, Graph Convolutional Network, Graph Attention neTwork) un’applicazione che ne mostri sia il funzionamento che l’importanza. Discutiamo, ulteriormente, l’implementazione di un algoritmo di classificazione basato su due varianti dell’architettura Graph Convolutional Network, addestrato e testato sul dataset PROTEINS, capace di classificare le proteine del dataset in due categorie: enzimi e non enzimi.
5
Wengle, Emil. "Modelling Hierarchical Structures in Networks Using Graph Theory : With Application to Knowledge Networks in Graph Curricula." Thesis, Uppsala universitet, Signaler och system, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-415044.
Full textAbstract:
Community detection is a topic in network theory that involves assigning labels to nodes based on some distance measure or centrality index. Detecting communities within a network can be useful to perform information condensation. In this thesis we explore how to use the approach for pedagogical purposes, and more precisely to condense and visualise the networks of facts, concepts and procedures (also called Knowledge Components (KCs)) that are offered in higher education programmes. In details, we consider one of the most common quantities used to evaluate the goodness of a community classification, which is the concept of modularity. Detecting communities by computing the maximum possible modularity indexes is indeed usually desired, but this approach is generally unavailable because the associated optimisation problem is NP-complete. This is why practitioners use other algorithms, that instead of computing the optimum they rely on various heuristics to find communities: some use modularity directly, some start from the entire graph and divide it repeatedly, and some contain random elements. This thesis investigates the trade-offs of using different community detection algorithms and variations of the concept of modularity first in general terms, and then for the purpose of identifying communities in knowledge graphs associated to higher education programmes, which can be modelled as directed graphs of KCs. We discover, tweaking and applying these algorithms both on synthetic but also field data that the Louvain algorithm is among the better algorithms of those that we considered, which is mostly thanks to its efficiency. It does not produce a full hierarchy, however, so we recommend Fast Newman if hierarchy is important.
6
Al-Shimary, Abbas. "Applications of graph theory to quantum computation." Thesis, University of Leeds, 2013. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.608359.
Full textAbstract:
Systems with topologically ordered ground states are considered to be promising candidates for quantum memories. These systems are characterised by a degenerate ground eigenspace separated by an energy gap from the rest of the spectrum. Consequently, topologically ordered systems are resilient to local noise since local errors are suppressed by the gap. Often, knowledge of the gap is not available and a direct approach to the problem is impractical. The first half of this thesis considers the problem of estimating the energy gap of a general class of Hamiltonians in the thermodynamical limit. In particular, we consider a remarkable result from spectral graph theory known as Cheeger inequalities. Cheeger inequalities give an upper and lower bound on the spectral gap of discrete Laplaeians defined on a graph in terms of the geometric characteristics of the graph. We generalise this approach and we employ it to determine if a given discrete Hamiltonian is gapped or not in the thermodynamic limit. A large class of 2D topologically ordered systems, including the Kitaev toric code, were proven to be unstable against thermal fluctuations. There systems can store information for a finite time known as the memory lifetime. The second half of this thesis will be devoted to investigating possible theoretical ways to extend the lifetime of thc 2D toric code. Firstly, we investigate the effect lattice geometry has on the lifetime of the qubit toric code. Importantly, we demonstrate how lattice geometries can be employed to enhance topological systems with intrinsically biased couplings due to physical implementation. Secondly, we improve the error correction properties and lifetime of the generalised 2D toric code by using charge-modifying domain walls. Specifically, we show that we can inhibit the propagation of anyons by introducing domain walls, provided the masses of the anyon types of the model are imbalanced.
7
Rittenhouse, Michelle L. "Properties and Recent Applications in Spectral Graph Theory." VCU Scholars Compass, 2008. http://scholarscompass.vcu.edu/etd/1126.
Full textAbstract:
There are numerous applications of mathematics, specifically spectral graph theory, within the sciences and many other fields. This paper is an exploration of recent applications of spectral graph theory, including the fields of chemistry, biology, and graph coloring. Topics such as the isomers of alkanes, the importance of eigenvalues in protein structures, and the aid that the spectra of a graph provides when coloring a graph are covered, as well as others.The key definitions and properties of graph theory are introduced. Important aspects of graphs, such as the walks and the adjacency matrix are explored. In addition, bipartite graphs are discussed along with properties that apply strictly to bipartite graphs. The main focus is on the characteristic polynomial and the eigenvalues that it produces, because most of the applications involve specific eigenvalues. For example, if isomers are organized according to their eigenvalues, a pattern comes to light. There is a parallel between the size of the eigenvalue (in comparison to the other eigenvalues) and the maximum degree of the graph. The maximum degree of the graph tells us the most carbon atoms attached to any given carbon atom within the structure. The Laplacian matrix and many of its properties are discussed at length, including the classical Matrix Tree Theorem and Cayley's Tree Theorem. Also, an alternative approach to defining the Laplacian is explored and compared to the traditional Laplacian.
8
Simmons, Dayton C. (Dayton Cooper). "Applications of Rapidly Mixing Markov Chains to Problems in Graph Theory." Thesis, University of North Texas, 1993. https://digital.library.unt.edu/ark:/67531/metadc277740/.
Full textAbstract:
In this dissertation the results of Jerrum and Sinclair on the conductance of Markov chains are used to prove that almost all generalized Steinhaus graphs are rapidly mixing and an algorithm for the uniform generation of 2 - (4k + 1,4,1) cyclic Mendelsohn designs is developed.
9
Cohen, Nathann. "Three years of graphs and music : some results in graph theory and its applications." Phd thesis, Université Nice Sophia Antipolis, 2011. http://tel.archives-ouvertes.fr/tel-00645151.
Full textAbstract:
Cette thèse présente différents aperçus de problèmes de mathématiques discrètes en lien avec la théorie des graphes. Elle s'intéresse en particulier à la coloration de graphes, i.e. l'assignation de couleurs aux sommets (ou arêtes) d'un graphes sous certaines contraintes locales, notamment l'exclusion de motifs. Pour différents types de coloration (choisissabilité des sommets, des arêtes, coloration acyclique ou linéaire, ...), un état de l'art est présenté, accompagné de résultats d'existence sur les graphes planaires ou leurs sous-classes, ayant pour but de minimiser le nombre de couleurs nécessaires pour un degré maximum ou un degré moyen maximum (Mad) donnés. Cette thèse traite également de décompositions induites de graphes, et démontre qu'il existe pour tout graphe $H$ une suite infinie de graphes denses dont les arêtes peuvent être partitionnées en copies induites de $H$. Cette preuve requiert le formalisme des hypergraphes, pour lesquels un autre résultat de décomposition est démontré, i.e. une décomposition optimale de l'hypergraphe complet 3-régulier en hypergraphes $\alpha$-acycliques. La troisième parti porte sur des questions algorithmiques. Elles consistent en problèmes d'optimisation ou d'existence, motivés par le routage d'information dans les réseaux, analysés par le formalisme classique de complexité algorithmique, ou traitent de la recherche de sous-graphes dans le formalisme de la complexité paramétrée. Dans une quatrième partie sont considérés des problèmes de comptage issus de la chimie, suivis de la présentation de Programmes Linéaires Entiers utilisés dans le logiciel de mathématiques Sage.
10
Kim, Pilho. "E-model event-based graph data model theory and implementation /." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/29608.
Full textAbstract:
Thesis (Ph.D)--Electrical and Computer Engineering, Georgia Institute of Technology, 2010.Committee Chair: Madisetti, Vijay; Committee Member: Jayant, Nikil; Committee Member: Lee, Chin-Hui; Committee Member: Ramachandran, Umakishore; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.
11
Marchand-Maillet, Stephane. "Graph theory and discrete geometry for digital image analysis : theory and applications." Thesis, Imperial College London, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.267485.
Full text
12
Shiping, Liu. "Synthetic notions of curvature and applications in graph theory." Doctoral thesis, Universitätsbibliothek Leipzig, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-102197.
Full textAbstract:
The interaction between the study of geometric and analytic aspects of Riemannian manifolds and that of graphs is a very amazing subject. The study of synthetic curvature notions on graphs adds new contributions to this topic. In this thesis, we mainly study two kinds of synthetic curvature notions: the Ollivier-Ricci cuvature on locally finite graphs and the combinatorial curvature on infinite semiplanar graphs.
In the first part, we study the Ollivier-Ricci curvature. As known in Riemannian geometry, a lower Ricci curvature bound prevents geodesics from diverging too fast on average. We translate this Riemannian idea into a combinatorial setting using the Olliver-Ricci curvature notion. Note that on a graph, the analogue of geodesics starting in different directions, but eventually approaching each other again, would be a triangle. We derive lower and upper Ollivier-Ricci curvature bounds on graphs in terms of number of triangles, which is sharp for instance for complete graphs. We then describe the relation between Ollivier-Ricci curvature and the local clustering coefficient, which is an important concept in network analysis introduced by Watts-Strogatz.
Furthermore, positive lower boundedness of Ollivier-Ricci curvature for neighboring vertices imply the existence of at least one triangle. It turns out that the existence of triangles can also improve Lin-Yau\'s curvature dimension inequality on graphs and then produce an implication from Ollivier-Ricci curvature lower boundedness to the curvature dimension inequality.
The existence of triangles prevents a graph from being bipartite. A finite graph is bipartite if and only if its largest eigenvalue equals 2. Therefore it is natural that Ollivier-Ricci curvature is closely related to the largest eigenvalue estimates. We combine Ollivier-Ricci curvature notion with the neighborhood graph method developed by Bauer-Jost to study the spectrum estimates of a finite graph. We can always obtain nontrivial estimates on a non-bipartite graph even if its curvature is nonpositive. This answers one of Ollivier\'s open problem in the finite graph setting.
In the second part of this thesis, we study systematically infinite semiplanar graphs with nonnegative combinatorial curvature. Unlike the previous Gauss-Bonnet formula approach, we explore an Alexandrov approach based on the observation that the nonnegative combinatorial curvature on a semiplanar graph is equivalent to nonnegative Alexandrov curvature on the surface obtained by replacing each face by a regular polygon of side length one with the same facial degree and gluing the polygons along common edges.
Applying Cheeger-Gromoll splitting theorem on the surface, we give a metric classification of infinite semiplanar graphs with nonnegative curvature. We also construct the graphs embedded into the projective plane minus one point. Those constructions answer a question proposed by Chen.
We further prove the volume doubling property and Poincare inequality which make the running of Nash-Moser iteration possible. We in particular explore the volume growth behavior on Archimedean tilings on a plane and prove that they satisfy a weak version of relative volume comparison with constant 1.
With the above two basic inequalities in hand, we study the geometric function theory of infinite semiplanar graphs with nonnegative curvature. We obtain the Liouville type theorem for positive harmonic functions, the parabolicity. We also prove a dimension estimate for polynomial growth harmonic functions, which is an extension of the solution of Colding-Minicozzi of a conjecture of Yau in Riemannian geometry.
13
Sutinuntopas, Somporn. "Applications of Graph Theory and Topology to Combinatorial Designs." Thesis, University of North Texas, 1988. https://digital.library.unt.edu/ark:/67531/metadc331968/.
Full textAbstract:
This dissertation is concerned with the existence and the isomorphism of designs. The first part studies the existence of designs. Chapter I shows how to obtain a design from a difference family. Chapters II to IV study the existence of an affine 3-(p^m,4,λ) design where the v-set is the Galois field GF(p^m). Associated to each prime p, this paper constructs a graph. If the graph has a 1-factor, then a difference family and hence an affine design exists. The question arises of how to determine when the graph has a 1-factor. It is not hard to see that the graph is connected and of even order. Tutte's theorem shows that if the graph is 2-connected and regular of degree three, then the graph has a 1-factor. By using the concept of quadratic reciprocity, this paper shows that if p Ξ 53 or 77 (mod 120), the graph is almost regular of degree three, i.e., every vertex has degree three, except two vertices each have degree tow. Adding an extra edge joining the two vertices with degree tow gives a regular graph of degree three. Also, Tutte proved that if A is an edge of the graph satisfying the above conditions, then it must have a 1-factor which contains A. The second part of the dissertation is concerned with determining if two designs are isomorphic. Here the v-set is any group G and translation by any element in G gives a design automorphism. Given a design B and its difference family D, two topological spaces, B and D, are constructed. We give topological conditions which imply that a design isomorphism is a group isomorphism.
14
Ahadi, Moghaddam Masoumeh [Verfasser], and Dietmar [Akademischer Betreuer] Schweigert. "Graph Coloring Applications and Defining Sets in Graph Theory / Masoumeh Ahadi Moghaddam ; Betreuer: Dietmar Schweigert." Kaiserslautern : Technische Universität Kaiserslautern, 2017. http://d-nb.info/1127044435/34.
Full text
15
Consoli, Sergio. "The development and application of metaheuristics for problems in graph theory : a computational study." Thesis, Brunel University, 2008. http://bura.brunel.ac.uk/handle/2438/3061.
Full textAbstract:
It is known that graph theoretic models have extensive application to real-life discrete optimization problems. Many of these models are NP-hard and, as a result, exact methods may be impractical for large scale problem instances. Consequently, there is a great interest in developing e±cient approximate methods that yield near-optimal solutions in acceptable computational times. A class of such methods, known as metaheuristics, have been proposed with success. This thesis considers some recently proposed NP-hard combinatorial optimization problems formulated on graphs. In particular, the min- imum labelling spanning tree problem, the minimum labelling Steiner tree problem, and the minimum quartet tree cost problem, are inves- tigated. Several metaheuristics are proposed for each problem, from classical approximation algorithms to novel approaches. A compre- hensive computational investigation in which the proposed methods are compared with other algorithms recommended in the literature is reported. The results show that the proposed metaheuristics outper- form the algorithms recommended in the literature, obtaining optimal or near-optimal solutions in short computational running times. In addition, a thorough analysis of the implementation of these methods provide insights for the implementation of metaheuristic strategies for other graph theoretic problems.
16
Huang, Zan. "GRAPH-BASED ANALYSIS FOR E-COMMERCE RECOMMENDATION." Diss., Tucson, Arizona : University of Arizona, 2005. http://etd.library.arizona.edu/etd/GetFileServlet?file=file:///data1/pdf/etd/azu%5Fetd%5F1167%5F1%5Fm.pdf&type=application/pdf.
Full text
17
Downs, M. L. N. "Mobius inversion of some classical groups and their application to the enumeration of regular hypermaps." Thesis, University of Southampton, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.381232.
Full text
18
Rautiainen, Mikko [Verfasser]. "Sequence to graph alignment : theory, practice and applications / Mikko Rautiainen." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2020. http://d-nb.info/1217656928/34.
Full text
19
Chen, Zhiqian. "Graph Neural Networks: Techniques and Applications." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/99848.
Full textAbstract:
Effective information analysis generally boils down to the geometry of the data represented by a graph. Typical applications include social networks, transportation networks, the spread of epidemic disease, brain's neuronal networks, gene data on biological regulatory networks, telecommunication networks, knowledge graph, which are lying on the non-Euclidean graph domain. To describe the geometric structures, graph matrices such as adjacency matrix or graph Laplacian can be employed to reveal latent patterns. This thesis focuses on the theoretical analysis of graph neural networks and the development of methods for specific applications using graph representation. Four methods are proposed, including rational neural networks for jump graph signal estimation, RemezNet for robust attribute prediction in the graph, ICNet for integrated circuit security, and CNF-Net for dynamic circuit deobfuscation.
For the first method, a recent important state-of-art method is the graph convolutional networks (GCN) nicely integrate local vertex features and graph topology in the spectral domain. However, current studies suffer from drawbacks: graph CNNs rely on Chebyshev polynomial approximation which results in oscillatory approximation at jump discontinuities since Chebyshev polynomials require degree $Omega$(poly(1/$epsilon$)) to approximate a jump signal such as $|x|$. To reduce complexity, RatioanlNet is proposed to integrate rational function and neural networks for graph node level embeddings. For the second method, we propose a method for function approximation which suffers from several drawbacks: non-robustness and infeasibility issue; neural networks are incapable of extracting analytical representation; there is no study reported to integrate the superiorities of neural network and Remez. This work proposes a novel neural network model to address the above issues. Specifically, our method utilizes the characterizations of Remez to design objective functions. To avoid the infeasibility issue and deal with the non-robustness, a set of constraints are imposed inspired by the equioscillation theorem of best rational approximation. The third method proposes an approach for circuit security. Circuit obfuscation is a recently proposed defense mechanism to protect digital integrated circuits (ICs) from reverse engineering. Estimating the deobfuscation runtime is a challenging task due to the complexity and heterogeneity of graph-structured circuit, and the unknown and sophisticated mechanisms of the attackers for deobfuscation. To address the above-mentioned challenges, this work proposes the first graph-based approach that predicts the deobfuscation runtime based on graph neural networks. The fourth method proposes a representation for dynamic size of circuit graph. By analyzing SAT attack method, a conjunctive normal form (CNF) bipartite graph is utilized to characterize the complexity of this SAT problem. To overcome the difficulty in capturing the dynamic size of the CNF graph, an energy-based kernel is proposed to aggregate dynamic features.Doctor of Philosophy
Graph data is pervasive throughout most fields, including pandemic spread network, social network, transportation roads, internet, and chemical structure. Therefore, the applications modeled by graph benefit people's everyday life, and graph mining derives insightful opinions from this complex topology. This paper investigates an emerging technique called graph neural newton (GNNs), which is designed for graph data mining. There are two primary goals of this thesis paper: (1) understanding the GNNs in theory, and (2) apply GNNs for unexplored and values real-world scenarios. For the first goal, we investigate spectral theory and approximation theory, and a unified framework is proposed to summarize most GNNs. This direction provides a possibility that existing or newly proposed works can be compared, and the actual process can be measured. Specifically, this result demonstrates that most GNNs are either an approximation for a function of graph adjacency matrix or a function of eigenvalues. Different types of approximations are analyzed in terms of physical meaning, and the advantages and disadvantages are offered. Beyond that, we proposed a new optimization for a highly accurate but low efficient approximation. Evaluation of synthetic data proves its theoretical power, and the tests on two transportation networks show its potentials in real-world graphs. For the second goal, the circuit is selected as a novel application since it is crucial, but there are few works. Specifically, we focus on a security problem, a high-value real-world problem in industry companies such as Nvidia, Apple, AMD, etc. This problem is defined as a circuit graph as apply GNN to learn the representation regarding the prediction target such as attach runtime. Experiment on several benchmark circuits shows its superiority on effectiveness and efficacy compared with competitive baselines. This paper provides exploration in theory and application with GNNs, which shows a promising direction for graph mining tasks. Its potentials also provide a wide range of innovations in graph-based problems.
20
Pengelly, Alan David. "The application of graph theory to the synthesis of protocol converters via the interface equation." Thesis, Open University, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.282279.
Full text
21
Koessler, Denise Renee. "A Predictive Model for Secondary RNA Structure Using Graph Theory and a Neural Network." Digital Commons @ East Tennessee State University, 2010. https://dc.etsu.edu/etd/1684.
Full textAbstract:
In this work we use a graph-theoretic representation of secondary RNA structure found in the database RAG: RNA-As-Graphs. We model the bonding of two RNA secondary structures to form a larger structure with a graph operation called merge. The resulting data from each tree merge operation is summarized and represented by a vector. We use these vectors as input values for a neural network and train the network to recognize a tree as RNA-like or not based on the merge data vector.
The network correctly assigned a high probability of RNA-likeness to trees identified as RNA-like in the RAG database, and a low probability of RNA-likeness to those classified as not RNA-like in the RAG database. We then used the neural network to predict the RNA-likeness of all the trees of order 9. The use of a graph operation to theoretically describe the bonding of secondary RNA is novel.
22
Thwaites, Peter. "Chain event graphs : theory and application." Thesis, University of Warwick, 2008. http://wrap.warwick.ac.uk/49194/.
Full textAbstract:
This thesis is concerned with the Graphical model known as the Chain Event Graph (CEG) [1][60][61], and develops the theory that appears in the currently published papers on this work. Results derived are analogous to those produced for Bayesian Networks (BNs), and I show that for asymmetric problems the CEG is generally superior to the BN both as a representation of the problem and as an analytical tool. The CEG is designed to embody the conditional independence structure of problems whose state spaces are asymmetric and do not admit a natural Product Space structure. In this they differ from BNs and other structures with variable-based topologies. Chapter 1 details researchers' attempts to adapt BNs to model such problems, and outlines the advantages CEGs have over these adaptations. Chapter 2 describes the construction of CEGs. In chapter 3I create a semantic structure for the reading of CEGs, and derive results expressible in the form of context-specific conditional independence statements, that allow us to delve much more deeply into the independence structure of a problem than we can do with BNs. In chapter 4I develop algorithms for the updating of a CEG following observation of an event, analogous to the Local Message Passing algorithms used with BNs. These are more efficient than the BN-based algorithms when used with asymmetric problems. Chapter 5 develops the theory of Causal manipulation of CEGs, and introduces the singular manipulation, a class of interventions containing the set of interventions possible with BNs. I produce Back Door and Front Door Theorems analogous to those of Pearl [42], but more flexible as they allow asymmetric manipulations of asymmetric problems. The ideas and results of chapters 2 to 5 are summarised in chapter 6.
23
Andersen, Aaron. "GraphShop: An Interactive Software Environment for Graph Theory Research and Applications." DigitalCommons@USU, 2011. https://digitalcommons.usu.edu/etd/896.
Full textAbstract:
Graph Theory is the mathematical study of the structure of abstract relationships between objects. Although these constructions (graphs) are themselves purely theoretical, their ability to model pair-wise relationships in systems of arbitrary complexity yields abundant direct correspondence with numerous important physical and societal systems in the real world. Additionally, the simple discrete nature of fundamental graph structures allows for easy pseudo-geometric visualization of graphs in a wide variety of ways. Taken together, these two properties suggest that graph theory teaching, research, and applications would benefit greatly from the use of a unified software environment for graph construction, interaction, and visualization.
Based on this need, a comprehensive survey was undertaken of existing graph theory software packages, programs, and libraries to determine the suitability of each for use as a graph theory teaching and research tool. Some of the desired components (especially in the realm of graph visualization) were found to be implemented in several current tools and systems, but no single system was located with the ability to perform all such functions together in a coordinated way.
Graph Shop (the Graph Theory Workshop) is a new software package for graph theory research and applications. It was designed to be usable by students and graph theory beginners yet powerful enough to assist with advanced graph theory research. It runs on a variety of platforms and is available for free under the GNU GPL open source license.
24
Sau, Ignasi. "Optimization in Graphs under Degree Constraints. Application to Telecommunication Networks." Phd thesis, Université de Nice Sophia-Antipolis, 2009. http://tel.archives-ouvertes.fr/tel-00429092.
Full textAbstract:
La première partie de cette thèse s'intéresse au groupage de trafic dans les réseaux de télécommunications. La notion de groupage de trafic correspond à l'agrégation de flux de faible débit dans des conduits de plus gros débit. Cependant, à chaque insertion ou extraction de trafic sur une longueur d'onde il faut placer dans le noeud du réseau un multiplexeur à insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilisée dans le noeud, ce qui représente un coût d'équipements important. Les objectifs du groupage de trafic sont d'une part le partage efficace de la bande passante et d'autre part la réduction du coût des équipements de routage. Nous présentons des résultats d'inapproximabilité, des algorithmes d'approximation, un nouveau modèle qui permet au réseau de pouvoir router n'importe quel graphe de requêtes de degré borné, ainsi que des solutions optimales pour deux scénarios avec trafic all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de manière dynamique. La deuxième partie de la thèse s'intéresse aux problèmes consistant à trouver des sous-graphes avec contraintes sur le degré. Cette classe de problèmes est plus générale que le groupage de trafic, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donné avec contraintes sur le degré, tout en optimisant un paramètre du graphe (très souvent, le nombre de sommets ou d'arêtes). Nous présentons des algorithmes d'approximation, des résultats d'inapproximabilité, des études sur la complexité paramétrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une méthodologie générale qui permet de résoudre efficacement cette classe de problèmes (et de manière plus générale, la classe de problèmes tels qu'une solution peut être codé avec une partition d'un sous-ensemble des sommets) pour les graphes plongés dans une surface. Finalement, plusieurs annexes présentent des résultats sur des problèmes connexes.
25
Meeks, Kitty M. F. T. "Graph colourings and games." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:a805a379-f891-4250-9a7d-df109f9f52e2.
Full textAbstract:
Graph colourings and combinatorial games are two very widely studied topics in discrete mathematics. This thesis addresses the computational complexity of a range of problems falling within one or both of these subjects. Much of the thesis is concerned with the computational complexity of problems related to the combinatorial game (Free-)Flood-It, in which players aim to make a coloured graph monochromatic ("flood" the graph) with the minimum possible number of flooding operations; such problems are known to be computationally hard in many cases. We begin by proving some general structural results about the behaviour of the game, including a powerful characterisation of the number of moves required to flood a graph in terms of the number of moves required to flood its spanning trees; these structural results are then applied to prove tractability results about a number of flood-filling problems. We also consider the computational complexity of flood-filling problems when the game is played on a rectangular grid of fixed height (focussing in particular on 3xn and 2xn grids), answering an open question of Clifford, Jalsenius, Montanaro and Sach. The final chapter concerns the parameterised complexity of list problems on graphs of bounded treewidth. We prove structural results determining the list edge chromatic number and list total chromatic number of graphs with bounded treewidth and large maximum degree, which are special cases of the List (Edge) Colouring Conjecture and Total Colouring Conjecture respectively. Using these results, we show that the problem of determining either of these quantities is fixed parameter tractable, parameterised by the treewidth of the input graph. Finally, we analyse a list version of the Hamilton Path problem, and prove it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.
26
Freeman, Andre. "Dual-Eulerian graphs with applications to VLSI design." Link to electronic thesis, 2003. http://www.wpi.edu/Pubs/ETD/Available/etd-0430103-155731/.
Full text
27
Sawant, Vivek Manohar. "A hypertext application and system for G-net and the complementary relationship between graph theory and hypertext." Virtual Press, 1993. http://liblink.bsu.edu/uhtbin/catkey/879843.
Full textAbstract:
Many areas of computer science use graph theory and thus benefit from research in graph theory. Some of the important activities involved in graph theory work are the study of concepts, algorithm development, and theorem proving. These can be facilitated by providing computerized tools for graph drawing, algorithm animation and accessing graph theory information bases. Project G-Net is aimed at developing a set of such tools.Project G-Net has chosen to provide the tools in hypertext form based on the analysis of users' requirements. The project is presently developing a hypertext application and a hypertext system for providing the above set of tools. In the process of this development various issues pertaining to hypertext authoring, hypertext usability and application of graph theory to hypertext are being explored.The focus of this thesis is in proving that hypertext approach is most appropriate for realizing the goals of the G-Net project. The author was involved in the research that went into analysis of requirements, design of hypertext application and system, and the investigation of the complementary relationship between graph theory and hypertext.Department of Computer Science
28
Hamadi, Riad. "Méthodes de décompositions de domaines pour la résolution des CSP : application au système OSIRIS." Université Joseph Fourier (Grenoble ; 1971-2015), 1997. http://www.theses.fr/1997GRE10203.
Full textAbstract:
La premiere partie de ce travail presente une approche de decomposition de domaines pour resoudre les problemes de satisfaction de contraintes (csp) discrets et continus lineaires. L'approche repose sur : 1 - la representation d'un csp par un graphe appele la micro-structure du csp. 2- la decomposition du csp en sous-csp definis a partir de cliques maximales de la micro-structure. Dans la premiere partie, on presente la methode de decomposition de domaine developpee par jegou en 1993 pour resoudre les csp binaires discrets. Puis on propose une extension de cette methode pour resoudre les csp discrets n-aires et les csp continus lineaires. La seconde partie de ce travail presente l'utilisation de la methode de decomposition de domaine pour definir et resoudre les csp discrets et continus lineaires dans un systeme de representation de connaissances, osiris, ainsi que l'utilisation de micro-structures pour le classement d'objets.
29
Damaj, Samer. "SWH, application "Small-world" à la génération des réseaux d'interconnexion pour les architectures massivement parallèles." Brest, 2011. http://www.theses.fr/2011BRES2076.
Full textAbstract:
Les possibilités d'intégration sont de plus en plus importantes et le nombre de transistors disponibles sur un composant n'est plus aussi critique que dans le passé. Cependant les structures de traitement du type monoprocesseur ne bénéficient plus de cette augmentation de ressources et on voit apparaître des composants du type MP Soc (multiprocessors on Chip) qui intègre plusieurs coeurs de processeur sur une même puce. Le problème consiste donc à faire passer à l'échelle des architectures systèmes du type MIMD (Multiple Instruction stream Multiple Data stream). Si on considère des coeurs de processeur complexe alors le problème reste actuellement assez maîtrisable car leur nombre reste limité (2 voit 4 processeurs). Par contre l'utilisation de noeuds de traitement de plus petite taille autorise l'intégration de dizaines voire de centaines de processeurs sur un même circuit. Les besoins en puissance de calcul ne se satisfont plus des limites rencontrées sur des processeurs complexes. La généralisation des composants du type MPSoC qui intègrent un nombre toujours plus important de processeurs sur une puce. Cependant, interconnecter un grand nombre de processeurs sur une puce est un délicat. Essentiellement, les structures adaptées aux contraintes de la puce sont trop peu générales, et les schémas de l’interconnexion plus globale engendrent des coûts de fabrication trop élevés. Ce problème se décompose en deux sous problèmes intimement liés qui sont la recherche d'une topologie permettant d'atteindre un niveau de connectivité acceptable et le coût matériel de sa réalisation. C'est dans ce dernier cas qui s'inscrit le contexte scientifique de ce mémoire. Les concepteurs se basent sur des différentes architectures pour réaliser des puces. Les architectures à mémoire partagée où il y a une saturation d’accès mémoire avec un grand nombre de PEs (Processeurs Élémentaires) comme par exemple TILERA Corporation. Les architectures à mémoire distribué où il se manifeste le problème des programmes fortement communicants. Ce type d'architecture est structuré autour d'un Noc (Network-on-Chip). De nombreuses études ont déjà été réalisées sur la problématique des architectures et de leurs réalisations avec pour motivations de trouver une manière élégante de supporter des Pes qui est de plus en plus nombreux et rapide en limitant le nombre de fils et pour obtenir des réseaux réguliers où le coût et le temps de développement du layout sont très court. Pour cette raison, nous sommes à la recherche d'une nouvelle plate-forme homogène avec des multicoeurs réguliers et massivement parallèles. C'est dans ce dernier cas qui s'inscrit le contexte industriel de ce mémoire de thèse. Pour des raisons techniques, il faut rendre les circuits homogènes, réguliers et denses parce que le coût et le temps de développement du layout d'un circuit non régulier sont très longs. Pour cette raison, il faut s'appuyer sur des architectures massivement parallèles. Les processeurs doivent communiquer entre eux, ils sont donc connectés via un réseau qui implémente une topologie. Pour une topologie donnée, on dispose de métriques grossières telles que le nombre de noeuds (le nombre de sommets dans un graphe donné), le degré (le nombre de liens entrants et sortants pour chaque sommet dans ce graphe donné) et le diamètre (la distance maximale entre deux noeuds ou sommets quelconques dans le graphe). Dans ce cas, comme on veut un circuit régulier, où les CPUs sont organisés en grille 2D pour les techniques actuels et éventuellement 3D pour les futurs techniques alors il faut obtenir le coût silicium pour mapper la topologie choisie sur cette grille. Le passage de la topologie (mapping) à la réalisation sera qualifié de placement-routage" physique (le terme "placement" veut dire de placer les sommets de ce graphe donné sur une grille 2D et le terme "routage" veut dire de faire communiquer ces sommets entre eux)Graphs with a minimum diameter have applications in the design of building-block switching systems, communication networks, and distributed computer systems. Several methods of constructing directed graphs with a small diameter are proposed. First, the dissertation presents as background several (delta, D) graphs including the Hypercube and de Bruijn. It shows the major disadvantages when implementing these topologies in practice for large scale. To achieve our goal, we propose a regular graph called Small World Heuristic (SWH) suitable for large parallel computers. This graph has a maximum degree ! and a small diameter D, while maintaining an acceptable level of connectivity. We show that this heuristic can connect on short distance thousands of nodes as little as 4 links per node. ̕Finally, we present a new integrated placement and routing algorithm to implement this heuristic on 2D VLSI
30
Donachy, Shaun. "Spiking Neural Networks: Neuron Models, Plasticity, and Graph Applications." VCU Scholars Compass, 2015. http://scholarscompass.vcu.edu/etd/3984.
Full textAbstract:
Networks of spiking neurons can be used not only for brain modeling but also to solve graph problems. With the use of a computationally efficient Izhikevich neuron model combined with plasticity rules, the networks possess self-organizing characteristics. Two different time-based synaptic plasticity rules are used to adjust weights among nodes in a graph resulting in solutions to graph prob- lems such as finding the shortest path and clustering.
31
So, Anthony Man-Cho. "A semidefinite programming approach to the graph realization problem : theory, applications and extensions /." May be available electronically:, 2007. http://proquest.umi.com/login?COPT=REJTPTU1MTUmSU5UPTAmVkVSPTI=&clientId=12498.
Full text
32
Radke, Hendrik [Verfasser], Annegret [Akademischer Betreuer] Habel, and Andy [Akademischer Betreuer] Schürr. "A Theory of HR* Graph Conditions and their Application to Meta-Modeling / Hendrik Radke. Betreuer: Annegret Habel ; Andy Schürr." Oldenburg : BIS der Universität Oldenburg, 2016. http://d-nb.info/1104932075/34.
Full text
33
Radke, Hendrik Verfasser], Annegret [Akademischer Betreuer] Habel, and Andy [Akademischer Betreuer] [Schürr. "A Theory of HR* Graph Conditions and their Application to Meta-Modeling / Hendrik Radke. Betreuer: Annegret Habel ; Andy Schürr." Oldenburg : BIS der Universität Oldenburg, 2016. http://nbn-resolving.de/urn:nbn:de:gbv:715-oops-28845.
Full text
34
Reutter, Juan L. "Graph patterns : structure, query answering and applications in schema mappings and formal language theory." Thesis, University of Edinburgh, 2013. http://hdl.handle.net/1842/8931.
Full textAbstract:
Graph data appears in a variety of application domains, and many uses of it, such as querying, matching, and transforming data, naturally result in incompletely specified graph data, i.e., graph patterns. Queries need to be posed against such data, but techniques for querying patterns are generally lacking, and even simple properties of graph patterns, such as the languages needed to specify them, are not well understood. In this dissertation we present several contributions in the study of graph patterns. We analyze how to query them and how to use them as queries. We also analyze some of their applications in two different contexts: schema mapping specification and data exchange for graph databases, and formal language theory. We first identify key features of patterns, such as node and label variables and edges specified by regular expressions, and define a classification of patterns based on them. Next we study how to answer standard graph queries over graph patterns, and give precise characterizations of both data and combined complexity for each class of patterns. If complexity is high, we do further analysis of features that lead to intractability, as well as lower-complexity restrictions that guarantee tractability. We then turn to the the study of schema mappings for graph databases. As for relational and XML databases, our mapping languages are based on patterns. They subsume all previously considered mapping languages for graph databases, and are capable of expressing many data exchange scenarios in the graph database context. We study the problems of materializing solutions and query answering for data exchange under these mappings, analyze their complexity, and identify relevant classes of mappings and queries for which these problems can be solved efficiently. We also introduce a new model of automata that is based on graph patterns, and define two modes of acceptance for them. We show that this model has applications not only in graph databases but in several other contexts. We study the basic properties of such automata, and the key computational tasks associated with them.
35
Kohl, Florian [Verfasser]. "Lattice Polytopes - Applications and Properties : Ehrhart Theory, Graph Colorings, and Level Algebras / Florian Kohl." Berlin : Freie Universität Berlin, 2018. http://d-nb.info/1176639625/34.
Full text
36
Espinosa, Kristofer, and Tam Vu. "Graph theory applications in the energy sector : From the perspective of electric utility companies." Thesis, KTH, Skolan för industriell teknik och management (ITM), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-279516.
Full textAbstract:
Graph theory is a mathematical study of objects and their pairwise relations, also known as nodes and edges. The birth of graph theory is often considered to take place in 1736 when Leonhard Euler tried to solve a problem involving seven bridges of Königsberg in Prussia. In more recent times, graphs has caught the attention of companies from many industries due to its power of modelling and analysing large networks. This thesis investigates the usage of graph theory in the energy sector for a utility company, in particular Fortum whose activities consist of, but not limited to, production and distribution of electricity and heat. The output of the thesis is a wide overview of graph-theoretic concepts and their applications, as well as an evaluation of energy-related use-cases where some concepts are put into deeper analysis. The chosen use-case within the scope of this thesis is feature selection for electricity price forecasting. Feature selection is a process for reducing the number of features, also known as input variables, typically before a regression model is built to avoid overfitting and to increase model interpretability. Five graph-based feature selection methods with different points of view are studied. Experiments are conducted on realistic data sets with many features to verify the legitimacy of the methods. One of the data sets is owned by Fortum and used for forecasting the electricity price, among other important quantities. The obtained results look promising according to several evaluation metrics and can be used by Fortum as a support tool to develop prediction models. In general, a utility company can likely take advantage graph theory in many ways and add value to their business with enriched mathematical knowledge.Grafteori är ett matematiskt område där objekt och deras parvisa relationer, även kända som noder respektive kanter, studeras. Grafteorins födsel anses ofta ha ägt rum år 1736 när Leonhard Euler försökte lösa ett problem som involverade sju broar i Königsberg i Preussen. På senare tid har grafer fått uppmärksamhet från företag inom flera branscher på grund av dess kraft att modellera och analysera stora nätverk. Detta arbete undersöker användningen av grafteori inom energisektorn för ett allmännyttigt företag, närmare bestämt Fortum, vars verksamhet består av, men inte är begränsad till, produktion och distribution av el och värme. Arbetet resulterar i en bred genomgång av grafteoretiska begrepp och deras tillämpningar inom både allmänna tekniska sammanhang och i synnerhet energisektorn, samt ett fallstudium där några begrepp sätts in i en djupare analys. Den valda fallstudien inom ramen för arbetet är variabelselektering för elprisprognostisering. Variabelselektering är en process för att minska antalet ingångsvariabler, vilket vanligtvis genomförs innan en regressions- modell skapas för att undvika överanpassning och öka modellens tydbarhet. Fem grafbaserade metoder för variabelselektering med olika ståndpunkter studeras. Experiment genomförs på realistiska datamängder med många ingångsvariabler för att verifiera metodernas giltighet. En av datamängderna ägs av Fortum och används för att prognostisera elpriset, bland andra viktiga kvantiteter. De erhållna resultaten ser lovande ut enligt flera utvärderingsmått och kan användas av Fortum som ett stödverktyg för att utveckla prediktionsmodeller. I allmänhet kan ett energiföretag sannolikt dra fördel av grafteori på många sätt och skapa värde i sin affär med hjälp av berikad matematisk kunskap
37
Zaslavskiy, Mikhail. "Graph matching and its application in computer vision and bioinformatics." Paris, ENMP, 2010. http://www.theses.fr/2010ENMP1659.
Full textAbstract:
Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de noeuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendents dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiquesThe graph matching problem is among the most important challenges of graph processing, and plays a central role in various fields of pattern recognition. We propose an approximate method for labeled weighted graph matching, based on a convex-concave programming approach which can be applied to the matching of large sized graphs. This method allows to easily integrate information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching. One of the interesting applications of the graph matching problem is the alignment of protein-protein interaction networks. This problem is important when investigating evolutionary conserved pathways or protein complexes across species, and to help in the identification of functional orthologs through the detection of conserved interactions. We reformulate PPI alignment as a graph matching problem, and study how state-of-the-art graph matching algorithms can be used for this purpose. In the classical formulation of graph matching, only one-to-one correspondences are considered, which is not always appropriate. In many applications, it is more interesting to consider many-to-many correspondences between graph vertices. We propose a reformulation of the many-to-many graph matching problem as a discrete optimization problem and we propose an approximate algorithm based on a continuous relaxation. In this thesis, we also present two interesting results in statistical machine translation and bioinformatics. We show how the phrase-based statistical machine translation decoding problem can be reformulated as a Traveling Salesman Problem. We also propose a new protein binding pocket similarity measure based on a comparison of 3D atom clouds
38
Burkhart, Craig. "Approval Voting Theory with Multiple Levels of Approval." Scholarship @ Claremont, 2012. https://scholarship.claremont.edu/hmc_theses/26.
Full textAbstract:
Approval voting is an election method in which voters may cast votes for as many candidates as they desire. This can be modeled mathematically by associating to each voter an approval region: a set of potential candidates they approve. In this thesis we add another level of approval somewhere in between complete approval and complete disapproval. More than one level of approval may be a better model for a real-life voter's complex decision making. We provide a new definition for intersection that supports multiple levels of approval. The case of pairwise intersection is studied, and the level of agreement among voters is studied under restrictions on the relative size of each voter's preferences. We derive upper and lower bounds for the percentage of agreement based on the percentage of intersection.
39
Martinelli, Andres. "Advances in Functional Decomposition: Theory and Applications." Doctoral thesis, SICS, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:ri:diva-21180.
Full textAbstract:
Functional decomposition aims at finding efficient representations for Boolean functions. It is used in many applications, including multi-level logic synthesis, formal verification, and testing. This dissertation presents novel heuristic algorithms for functional decomposition. These algorithms take advantage of suitable representations of the Boolean functions in order to be efficient. The first two algorithms compute simple-disjoint and disjoint-support decompositions. They are based on representing the target function by a Reduced Ordered Binary Decision Diagram (BDD). Unlike other BDD-based algorithms, the presented ones can deal with larger target functions and produce more decompositions without requiring expensive manipulations of the representation, particularly BDD reordering. The third algorithm also finds disjoint-support decompositions, but it is based on a technique which integrates circuit graph analysis and BDD-based decomposition. The combination of the two approaches results in an algorithm which is more robust than a purely BDD-based one, and that improves both the quality of the results and the running time. The fourth algorithm uses circuit graph analysis to obtain non-disjoint decompositions. We show that the problem of computing non-disjoint decompositions can be reduced to the problem of computing multiple-vertex dominators. We also prove that multiple-vertex dominators can be found in polynomial time. This result is important because there is no known polynomial time algorithm for computing all non-disjoint decompositions of a Boolean function. The fifth algorithm provides an efficient means to decompose a function at the circuit graph level, by using information derived from a BDD representation. This is done without the expensive circuit re-synthesis normally associated with BDD-based decomposition approaches. Finally we present two publications that resulted from the many detours we have taken along the winding path of our research.
40
Guzman, Roca Juan Alberto. "Quantification of track-weighted functional connectivity longitudinally during Constraint Induced Movement Therapy for poststroke hemiparesis: An application of Graph Theory." The Ohio State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=osu1492621365041026.
Full text
41
Kissinger, Aleks. "Pictures of processes : automated graph rewriting for monoidal categories and applications to quantum computing." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:61fb3161-a353-48fc-8da2-6ce220cce6a2.
Full textAbstract:
This work is about diagrammatic languages, how they can be represented, and what they in turn can be used to represent. More specifically, it focuses on representations and applications of string diagrams. String diagrams are used to represent a collection of processes, depicted as "boxes" with multiple (typed) inputs and outputs, depicted as "wires". If we allow plugging input and output wires together, we can intuitively represent complex compositions of processes, formalised as morphisms in a monoidal category. While string diagrams are very intuitive, existing methods for defining them rigorously rely on topological notions that do not extend naturally to automated computation. The first major contribution of this dissertation is the introduction of a discretised version of a string diagram called a string graph. String graphs form a partial adhesive category, so they can be manipulated using double-pushout graph rewriting. Furthermore, we show how string graphs modulo a rewrite system can be used to construct free symmetric traced and compact closed categories on a monoidal signature. The second contribution is in the application of graphical languages to quantum information theory. We use a mixture of diagrammatic and algebraic techniques to prove a new classification result for strongly complementary observables. Namely, maximal sets of strongly complementary observables of dimension D must be of size no larger than 2, and are in 1-to-1 correspondence with the Abelian groups of order D. We also introduce a graphical language for multipartite entanglement and illustrate a simple graphical axiom that distinguishes the two maximally-entangled tripartite qubit states: GHZ and W. Notably, we illustrate how the algebraic structures induced by these operations correspond to the (partial) arithmetic operations of addition and multiplication on the complex projective line. The third contribution is a description of two software tools developed in part by the author to implement much of the theoretical content described here. The first tool is Quantomatic, a desktop application for building string graphs and graphical theories, as well as performing automated graph rewriting visually. The second is QuantoCoSy, which performs fully automated, model-driven theory creation using a procedure called conjecture synthesis.
42
Inkmann, Torsten. "Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/22583.
Full textAbstract:
Thesis (Ph. D.)--Mathematics, Georgia Institute of Technology, 2008.Committee Chair: Thomas, Robin; Committee Co-Chair: Cook, William J.; Committee Member: Dvorak, Zdenek; Committee Member: Parker, Robert G.; Committee Member: Yu, Xingxing.
43
Vellambi, Badri Narayanan. "Applications of graph-based codes in networks: analysis of capacity and design of improved algorithms." Diss., Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/37091.
Full textAbstract:
The conception of turbo codes by Berrou et al. has created a renewed interest in modern graph-based codes. Several encouraging results that have come to light since then have fortified the role these codes shall play as potential solutions for present and future communication problems.
This work focuses on both practical and theoretical aspects of graph-based codes. The
thesis can be broadly categorized into three parts. The first part of the thesis focuses on
the design of practical graph-based codes of short lengths. While both low-density parity-check
codes and rateless codes have been shown to be asymptotically optimal under the message-passing (MP) decoder, the performance of short-length codes from these families under MP decoding is starkly sub-optimal. This work first addresses the
structural characterization of stopping sets to understand this sub-optimality. Using this
characterization, a novel improved decoder that offers several orders of magnitude improvement in bit-error rates is introduced. Next, a novel scheme for the design of a good rate-compatible family of punctured codes is proposed.
The second part of the thesis aims at establishing these codes as a good tool to develop
reliable, energy-efficient and low-latency data dissemination schemes in networks. The problems of broadcasting in wireless multihop networks and that of unicast in delay-tolerant networks are investigated. In both cases, rateless coding is seen to offer an elegant means of achieving the goals of the chosen communication protocols. It was noticed that the ratelessness and the randomness in encoding process make this scheme
specifically suited to such network applications.
The final part of the thesis investigates an application of a specific class of codes called
network codes to finite-buffer wired networks. This part of the work aims at establishing a framework for the theoretical study and understanding of finite-buffer networks. The
proposed Markov chain-based method extends existing results to develop an iterative
Markov chain-based technique for general acyclic wired networks. The framework not only estimates the capacity of such networks, but also provides a means to monitor network traffic and packet drop rates on various links of the network.
44
Martinelli, Andrés. "Advances in Functional Decomposition: Theory and Applications." Doctoral thesis, KTH, Mikroelektronik och Informationsteknik, IMIT, 2006. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4135.
Full textAbstract:
Functional decomposition aims at finding efficient representations for Boolean functions. It is used in many applications, including multi-level logic synthesis, formal verification, and testing. This dissertation presents novel heuristic algorithms for functional decomposition. These algorithms take advantage of suitable representations of the Boolean functions in order to be efficient. The first two algorithms compute simple-disjoint and disjoint-support decompositions. They are based on representing the target function by a Reduced Ordered Binary Decision Diagram (BDD). Unlike other BDD-based algorithms, the presented ones can deal with larger target functions and produce more decompositions without requiring expensive manipulations of the representation, particularly BDD reordering. The third algorithm also finds disjoint-support decompositions, but it is based on a technique which integrates circuit graph analysis and BDD-based decomposition. The combination of the two approaches results in an algorithm which is more robust than a purely BDD-based one, and that improves both the quality of the results and the running time. The fourth algorithm uses circuit graph analysis to obtain non-disjoint decompositions. We show that the problem of computing non-disjoint decompositions can be reduced to the problem of computing multiple-vertex dominators. We also prove that multiple-vertex dominators can be found in polynomial time. This result is important because there is no known polynomial time algorithm for computing all non-disjoint decompositions of a Boolean function. The fifth algorithm provides an efficient means to decompose a function at the circuit graph level, by using information derived from a BDD representation. This is done without the expensive circuit re-synthesis normally associated with BDD-based decomposition approaches. Finally we present two publications that resulted from the many detours we have taken along the winding path of our research.QC 20100909
45
Vu, Duc Tam. "Applications of graph theory in the energy sector, demonstrated with feature selection in electricity price forecasting." Thesis, KTH, Optimeringslära och systemteori, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-276482.
Full textAbstract:
Graph theory is a mathematical study of objects and their pairwise relations, known as nodes and edges respectively. The birth of graph theory is often considered to take place in 1736 when the Swiss mathematician Leonhard Euler tried to solve a routing problem involving seven bridges of Königsberg in Prussia. In more recent times, graph theory has caught the attention of companies from all types of industries due to its power of modelling and analysing exceptionally large networks. This thesis investigates the usage of graph theory in the energy sector for a utility company, in particular Fortum whose activities consist of, but not limited to, production and distribution of electricity and heat. The output of the thesis is a wide overview of graph-theoretic concepts and their practical applications, as well as a study of a use-case where some concepts are put into deeper analysis. The chosen use-case within the scope of this thesis is feature selection - a process for reducing the number of features, also known as input variables, typically before a regression model is built to avoid overfitting and increase model interpretability. Five graph-based feature selection methods with different points of view are studied. Experiments are conducted on realistic data sets with many features to verify the legitimacy of the methods. One of the data sets is owned by Fortum and used for forecasting the electricity price, among other important quantities. The obtained results look promising according to several evaluation metrics and can be used by Fortum as a support tool to develop prediction models. In general, a utility company can likely take advantage graph theory in many ways and add value to their business with enriched mathematical knowledge.Grafteori är ett matematiskt område där objekt och deras parvisa relationer, även kallade noder respektive kanter, studeras. Grafteorins födsel anses ofta äga rum år 1736 när den schweiziske matematikern Leonhard Euler försökte lösa ett vägsökningsproblem som involverade sju broar av Königsberg i Preussen. På senare tid har grafteori fått uppmärksamhet från företag inom flera branscher på grund av dess kraft att modellera och analysera väsentligt stora nätverk. Detta arbete undersöker användningen av grafteori inom energisektorn för ett allmännyttigt företag, närmare bestämt Fortum vars verksamhet består av, dock ej begränsat till, produktion och distribution av elektricitet och värme. Arbetet resulterar i en bred översiktlig genomgång av grafteoretiska begrepp och deras praktiska tillämpningar, samt ett fallstudium där några begrepp sätts in i en djupare analys. Det valda fallstudiet inom ramen för arbetet är variabelselektering - en process för att minska antalet ingångsvariabler, vilket vanligtvis genomförs innan en regressionsmodell skapas för att undvika överanpassning och öka modellens tydbarhet. Fem grafbaserade metoder för variabelselektering med olika ståndpunkter studeras. Experiment genomförs på realistiska datamängder med många ingångsvariabler för att verifiera metodernas giltighet. En av datamängderna ägs av Fortum och används för att prognostisera elpriset, bland andra viktiga kvantiteter. De erhållna resultaten ser lovande ut enligt flera utvärderingsmått och kan användas av Fortum som ett stödverktyg för att utveckla prediktionsmodeller. I allmänhet kan ett energiföretag sannolikt dra fördel av grafteori på många sätt och skapa värde i sin affär med hjälp av berikad matematisk kunskap.
46
Managbanag, JR. "Application of Shortest-Path Network Analysis to Identify Genes that Modulate Longevity in Saccharomyces cerevisiae." VCU Scholars Compass, 2008. http://scholarscompass.vcu.edu/etd/1613.
Full textAbstract:
Shortest-path network analysis was employed to identify novel genes that modulate longevity in the baker’s yeast Saccharomyces cerevisiae. Based upon a set of previously reported genes associated with increased life span, a shortest path network algorithm was applied to a pre-existing protein-protein interaction dataset in order to construct a shortest-path longevity network. To validate this network, the replicative aging potential of 88 single gene deletion strains corresponding to predicted components of the shortest path longevity network was determined. The 88 single-gene deletion strains identified by a network approach are significantly enriched for mutation conferring both increased and decreased replicative life span when compared to a randomly selected set of 564 single-gene deletion strains or to the current data set available for the entire haploid deletion collection. In addition, previously unknown longevity genes were identified, several of which function in a longevity pathway believed to mediate life span extension in response to dietary restriction. This study represents the first biologically validated application of a network construct to the study of aging and rigorously demonstrates, also for the first time, that shortest path network analysis is a potentially powerful tool for predicting genes that function as potential modulators of aging.
47
Abuali, Faris Nabih. "Using determinant and cycle basis schemes in genetic algorithms for graph and network applications /." Access abstract and link to full text, 1995. http://0-wwwlib.umi.com.library.utulsa.edu/dissertations/fullcit/9529027.
Full text
48
Dymkou, Siarhei M. "Graph and 2-D optimization theory and their application for discrete simulation of gas transportation networks and industrial processes with repetitive operations." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=986155993.
Full text
49
Braunschweig, Bertrand. "Aides à l'interprétation de simulations dynamiques : Application aux modèles de cinétique chimique." Paris 9, 1998. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1998PA090018.
Full textAbstract:
La simulation dynamique est couramment utilisée dans de nombreux domaines scientifiques et techniques. Des simulateurs dynamiques sont mis entre les mains de plus en plus d’utilisateurs, grâce à l’accroissement des performances et aux progrès des interfaces homme machine, qui rend les modèles accessibles à tous. Mais les simulateurs sont toujours, et avant tout, des programmes qui produisent des séries de nombres à partir de séries de nombres, même si elles sont représentées par des graphiques. Cette thèse présente de nouvelles approches de l’interaction entre un simulateur numérique et son utilisateur. Le simulateur s’auto-examine pour fournir une interprétation de ses résultats, reposant sur une représentation des objets du domaine, exhibant les mécanismes cycliques dominants grâce à l’estimation de leurs gains instantanés, utilisant la notion d’épisodes pour découper la simulation en tranches homogènes, et accompagnant le tout de visualisations animées utilisant la structure du système modélisé. Ces nouvelles approches sont expérimentées dans le cadre de la modélisation en cinétique chimique, domaine d’application qui a un caractère exemplaire vue la variété des modèles et des comportements rencontrés; elles sont matérialisées au sein du programme Spike d’aide à la conduite d’expérimentation en cinétique chimique. Les mêmes concepts sont également mis en œuvre dans les deux domaines très différents que sont la propagation des ondes sismiques et la simulation de projet. L’ensemble a pour but d ‘apporter une contribution nouvelle pour la conception et la réalisation d’une véritable « intelligence des systèmes dynamiques »Numerous scientific and technical domains make constant use of dynamical simulations. Such simulators are put in the hands of a growing number of users. This phenomenon is due both to the extraordinary increase in computing performance, and to better graphical user interfaces which make simulation models easy to operate. But simulators are still computer programs which produce series of numbers from other series of numbers, even if they are displayed graphically. This thesis presents new interaction paradigms between a dynamical simulator and its user. The simulator produces a self-made interpretation of its results, thanks to a dedicated representation of its domain with objects. It shows dominant cyclic mechanisms identified by their instantaneous loop gain estimates, it uses a notion of episodes for splitting the simulation into homogeneous time intervals, and completes this by animations which rely on the graphical structure of the System. These new approaches are demonstrated with examples from Chemical kinetics, because of the generic and exemplary characteristics of the encountered behaviors. They are implemented in the Spike software, a Software Platform for Interactive Chemical Kinetics Experiments. Similar concepts are also shown in two other domains: interpretation of seismic wave propagation, and simulation of large projects. Altogether the thesis is a step towards the delivery of a "Systems dynamics intelligence"
50
Imbert, Michel. "Combinatoire des revêtements : cellulation des espaces de Hurwitz." Université Joseph Fourier (Grenoble), 1998. http://www.theses.fr/1998GRE10228.
Full textAbstract:
L'objet de cette these est l'etude combinatoire des revetements entre surfaces de riemann et de leurs espaces modulaires : les espaces de hurwitz. Les methodes utilisees sont graphiques : nous utilisons largement le concept de graphe epais. Nous donnons un algorithme de calcul des lacets d'homologie d'un tel graphe. Nous montrons le theoreme d'existence de riemann au niveau des graphes epais. Nous detaillons le processus, du a j. L. Harer et m. Kontsevich, realisant un graphe epais a n faces muni de longueurs d'aretes en une surface de riemann compacte privee de n piqures. Ce processus, bijectif par le theoreme de strebel, mene a une decomposition cellulaire connue et fondamentale des espaces de modules de surfaces de riemann compactes de genre fixe et privees de n piqures. Nous sommes alors en mesure de preciser la variation de la structure complexe en fonction des longueurs d'aretes (ce qui donne la continuite du processus), et de generaliser le processus aux revetements de surfaces de riemann compactes. Cela conduit a la decomposition cellulaire des espaces de hurwitz. Nous etudions un exemple ou l'espace de hurwitz s'identifie a une courbe modulaire. L'etude des revetements cycliques des tores permet de relier l'espace de hurwitz correspondant a des espaces de modules definis par e. Witten dans le cadre d'une conjecture generalisant celle demontree par m. Kontsevich. L'extension des resultats aux compactifications des espaces de modules et de hurwitz s'appuie sur le phenomene de retraction de boucles d'un graphe epais ne bordant pas des faces.