Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 59 for “"graph isomorphism"”.
-
Use of the spectrum in graph isomorphism
… and eigenvectors of the adjacency matrices of graphs to determine graph isomorphism. Two randomly chosen graphs will in general have different eigenvalues, and comparing the eigenvalues provides a first filter when checking for isomorphism. If the graphs are cospectral, we propose an algorithm …
-
Graph Isomorphism Algorithms Based on Trees and Paths.
… bounded algorithms are presented for testing isomorphism of two classes of graphs: the strongly regular graphs, which have been difficult for many previous isomorphism algorithms to process, and the compact graphs (graphs with diameter of 2 whose complements also have diameter of 2).The …
-
An Investigation into Graph Isomorphism Based Zero-Knowledge Proofs
… several ways. In this thesis, I investigate the graph isomorphism based zero-knowledge proofs protocol. My experiments and analyses suggest that graph isomorphism can easily be solved for many types of graphs and hence is not an ideal solution for implementing ZKP.
-
Approximate Sub-Graph Isomorphism For Watermarking Finite State Machine Hardware
… can be achieved by matching a directed graph representation of the watermark with a sub-graph in state transition graph representation of the FSM. We experiment with three approaches: a brute force method that provides a proof of concept, a greedy algorithm that provides excellent …
-
Attacks On Difficult Instances Of Graph Isomorphism: Sequential And Parallel Algorithms
The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard …
-
Distance based canonical labeling algorithms with applications to graph matching
Graphs are mathematical structures that encode pairwise relationships between objects, which are usually identified with labels. However, graphs can represent relationships between any kind of objects and a fundamental problem is to determine if two graphs are equivalent from a structural point of …
-
Characterizing Algorithmic Efficiencies through Concentration
… called degree of symmetry. In this arena, graph isomorphism is my problem of choice. Once again, my goal is to characterize the efficiency of algorithms, in particular parallel algorithms, for graph isomorphism based on a concentration-related parameter. In particular, I propose a parallel …
-
Quantum Computation and Isomorphism Testing
… we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical …
-
Quantum Symmetries Studied Through the Lens of Non-Local Games
… entanglement, and we will focus our study on the graph isomorphism game and the metric isometry game. Work in quantum information theory has led to quantum versions of many concepts in classical mathematics, including quantum graphs and quantum metric spaces. We generalize Banica’s construction of …
-
A visualization system for information retrieval and mining in high dimensional databases
… databases often requires solving variants of the graph isomorphism or subisomorphism problems. We also describe a graphic user interface which interacts with users to facilitate visualizing query results. We use 3D molecules (graphs) as illustrating examples, though our prototype is able to handle …
-
Computer generation of regular graphs
… of computer generation of non-isomorphic regular graphs of degree d on n points. The uork consists of a study of various properties and representations of regular graphs and a discussion of hov these might be useful in solving the isomorphism problem in the computer generation of regular graphs. …
-
An Attempt to Automate <i>NP</i>-Hardness Reductions via <i>SO</i>∃ Logic
… sentences are equivalent is as hard as GRAPH ISOMORPHISM, and prove that determining whether an arbitrary <i>SO</i>∃ sentence represents an <i>NP</i>-complete problem is undecidable.
-
On the Unique Tree Representation of Graphs
This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P4's, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is …
-
Listing Unique Fractional Factorial Designs
… therefore contain only designs unique up to isomorphism. There are two computational challenges in generating such catalogs. Firstly, testing two designs for isomorphism is computationally hard due to the large number of possible relabelings, and, secondly, the number of designs increases …
-
On the symmetry reduction method for Petri nets and similar formalisms
… group theory and from the algorithms for the graph isomorphism problem. The experimental results show that the new algorithms are competitive against the previous ones described in the literature. Data symmetries, i. e., state space symmetries produced by symmetric use of data values, of a …
-
A Complete Implementation of Graphlopedia: A Fingerprint Database for Graphs
… web app and database using Django for graphs that appear in mathematical literature that we have named Graphlopedia. Graphlopedia, hosted at graphlopedia.org, uses graph isomorphism testing and image classification to combine user submitted entries with automatically crawled e-print …
-
A novel framework for dynamic graph representation learning with mamba
<p>Dynamic graph embedding is a key technique for modeling temporal dependencies in evolving networks. While transformer-based models perform well, their quadratic complexity limits scalability on long graph sequences. This thesis compares transformer approaches with the Mamba architecture-a …
-
On the isomorphism problem for a class of bipartite graphs
The purpose of this thesis is to investigate the graph isomorphism problem for a special class of graphs. Each graph is characterized by its edge set, and a subgroup of its automorphism group, called the colour group. In particular, a simple, efficient algorithm for determining whether two graphs …
Page 1 of 3