No description available.

Zero-knowledge proofs protocols are effective interactive methods to prove a node's identity without disclosing any additional information other than the veracity of the proof. They are implementable in 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.

Synthesis of structures is a very difficult task even with only a small number of components that form a system; yet it is the catalyst of innovation. Molecular structures and nanostructures typically have a large number of similar components but different connections, which manifests a more challenging task for their synthesis. <p> This thesis presents a novel method and its related algorithms and computer programs for the synthesis of structures. This novel method is based on several concepts: (1) the structure is represented by a graph and further by the adjacency matrix; and (2) instead of only exploiting the eigenvalue of the adjacency matrix, both the eigenvalue and the eigenvector are exploited; specifically the components of the eigenvector have been found very useful in algorithm development. This novel method is called the Eigensystem method.<p> The complexity of the Eigensystem method is equal to that of the famous program called Nauty in the combinatorial world. However, the Eigensystem method can work for the weighted and both directed and undirected graph, while the Nauty program can only work for the non-weighted and both directed and undirected graph. The cause for this is the different philosophies underlying these two methods. The Nauty program is based on the recursive component decomposition strategy, which could involve some unmanageable complexities when dealing with the weighted graph, albeit no such an attempt has been reported in the literature. It is noted that in practical applications of structure synthesis, weighted graphs are more useful than non-weighted graphs for representing physical systems. <p> Pivoted at the Eigensystem method, this thesis presents the algorithms and computer programs for the three fundamental problems in structure synthesis, namely the isomorphism/automorphism, the unique labeling, and the enumeration of the structures or graphs.

This thesis studies the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. We begin by finding the eigenvalues of matrices describing the quantum walk for regular graphs. We also show that if two graphs are isomorphic, then the corresponding matrices produced by the procedure of Emms et al. are cospectral. We then look at the entries of the cube of the transition matrix and find an expression for the matrices produced by the procedure of Emms et al. in terms of the adjacency matrix and incidence matrices of the graph.

Synthesis of structures is a very difficult task even with only a small number of components that form a system; yet it is the catalyst of innovation. Molecular structures and nanostructures typically have a large number of similar components but different connections, which manifests a more challenging task for their synthesis. <p> This thesis presents a novel method and its related algorithms and computer programs for the synthesis of structures. This novel method is based on several concepts: (1) the structure is represented by a graph and further by the adjacency matrix; and (2) instead of only exploiting the eigenvalue of the adjacency matrix, both the eigenvalue and the eigenvector are exploited; specifically the components of the eigenvector have been found very useful in algorithm development. This novel method is called the Eigensystem method.<p> The complexity of the Eigensystem method is equal to that of the famous program called Nauty in the combinatorial world. However, the Eigensystem method can work for the weighted and both directed and undirected graph, while the Nauty program can only work for the non-weighted and both directed and undirected graph. The cause for this is the different philosophies underlying these two methods. The Nauty program is based on the recursive component decomposition strategy, which could involve some unmanageable complexities when dealing with the weighted graph, albeit no such an attempt has been reported in the literature. It is noted that in practical applications of structure synthesis, weighted graphs are more useful than non-weighted graphs for representing physical systems. <p> Pivoted at the Eigensystem method, this thesis presents the algorithms and computer programs for the three fundamental problems in structure synthesis, namely the isomorphism/automorphism, the unique labeling, and the enumeration of the structures or graphs.

This dissertation investigates the extraction of knowledge from a known environment. Virtual ontology – the extracted knowledge – is defined as a structure of a virtual environment with semantics. While many existing 3D reconstruction approaches can generate virtual environments without structure and related knowledge, the use of Metaearth architecture is proposed as a more descriptive data structure for virtual ontology. Its architecture consists of four layers: interactions and relationships between virtual components can be represented in the virtual space layer; and the library layers contribute to the design of large-scale virtual environments with less redundancy; and the mapping layer links the library layer to the virtual space layer; and the ontology layer functions as a context for the extracted knowledge. The dissertation suggests two construction methodologies. The first method generates a scene structure from a 2D image. Unlike other scene understanding techniques, the suggested method generates scene ontology without prior knowledge and human intervention. As an intermediate process, a new and effective fuzzy color-based over-segmentation method is suggested. The second method generates virtual ontology with 3D information using multi-view scenes. The many ambiguities in extracting 3D information are resolved by employing a new fuzzy dynamic programming method (FDP). The hybrid approach of FDP and 3D reconstruction method generates more accurate virtual ontology with 3D information. A virtual model is equipped with virtual ontology whereby contextual knowledge can be mapped into the Metaearth architecture via the proposed isomorphic matching method. The suggested procedure guarantees the automatic and autonomous processing demanded in virtual interaction analysis with far less effort and computational time.

This thesis studies the transition matrix of a quantum walk on strongly regular graphs. It is proposed by Emms, Hancock, Severini and Wilson in 2006, that the spectrum of a matrix based on the amplitudes of walks in the quantum walk, distinguishes strongly regular graphs. We begin by finding the eigenvalues of matrices describing the quantum walk for regular graphs. We also show that if two graphs are isomorphic, then the corresponding matrices produced by the procedure of Emms et al. are cospectral. We then look at the entries of the cube of the transition matrix and find an expression for the matrices produced by the procedure of Emms et al. in terms of the adjacency matrix and incidence matrices of the graph.

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. The intersection graph I (D)of the decomposition D has a vertex for each part of the partition and two parts A and B are adjacent iff they share a common node in H. If I (D) ≅ H, then D is an automorphic decomposition of H. In this paper we show how automorphic decompositions serve as a common generalization of configurations from geometry and graceful labelings on graphs. We will give several examples of automorphic decompositions as well as necessary conditions for their existence.

No description available.

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 instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representative--an approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nauty-like algorithms. This dissertation investigates why these graph families pose difficulty for individualization-refinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time--thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guide-tree data structure of the preceding technique to use a stronger vertex-invariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.