Relevant bibliographies by topics / Graph isomorphism

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Graph isomorphism'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 April 2022

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graph isomorphism.'

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.

Journal articles on the topic "Graph isomorphism"

1

Tang, C. S., and Tyng Liu. "The Degree Code—A New Mechanism Identifier." Journal of Mechanical Design 115, no. 3 (September 1, 1993): 627–30. http://dx.doi.org/10.1115/1.2919236.

Full text
Abstract:
An important step in the structural synthesis of mechanisms requires the identification of isomorphism between the graphs which represents the mechanism topology. Previously used methods for identifying graph isomorphism either yield incorrect results for some cases or their algorithms are computationally inefficient for this application. This paper describes a new isomorphism identification method which is well suited for the automated structural synthesis of mechanisms. This method uses a new and compact mathematical representation for a graph, called the Degree Code, to identify graph isomorphism. Isomorphic graphs have identical Degree Codes; nonisomorphic graphs have distinct Degree Codes. Therefore, by examining the Degree Codes of the graphs, graph isomorphism is easily and correctly identified. This Degree Code algorithm is simpler and more efficient than other methods for identifying isomorphism correctly. In addition, the Degree Code can serve as an effective nomenclature and storage system for graphs or mechanisms. Although this identification scheme was developed specifically for the structural synthesis of mechanisms, it can be applied to any area where graph isomorphism is a critical issue.
APA, Harvard, Vancouver, ISO, and other styles
2

RAJASEKARAN, SANGUTHEVAR, and VAMSI KUNDETI. "SPECTRUM BASED TECHNIQUES FOR GRAPH ISOMORPHISM." International Journal of Foundations of Computer Science 20, no. 03 (June 2009): 479–99. http://dx.doi.org/10.1142/s0129054109006693.

Full text
Abstract:
The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs.
APA, Harvard, Vancouver, ISO, and other styles
3

Messmer, B. T., and H. Bunke. "Error-Correcting Graph Isomorphism Using Decision Trees." International Journal of Pattern Recognition and Artificial Intelligence 12, no. 06 (September 1998): 721–42. http://dx.doi.org/10.1142/s0218001498000415.

Full text
Abstract:
In this paper we present a fast algorithm for the computation of error-correcting graph isomorphisms. The new algorithm is an extension of a method for exact subgraph isomorphism detection from an input graph to a set of a priori known model graphs, which was previously developed by the authors. Similar to the original algorithm, the new method is based on the idea of creating a decision tree from the model graphs. This decision tree is compiled off-line in a preprocessing step. At run time, it is used to find all error-correcting graph isomorphisms from an input graph to any of the model graphs up to a certain degree of distortion. The main advantage of the new algorithm is that error-correcting graph isomorphism detection is guaranteed to require time that is only polynomial in terms of the size of the input graph. Furthermore, the time complexity is completely independent of the number of model graphs and the number of edges in each model graph. However, the size of the decision tree is exponential in the size of the model graphs and the degree of error. Nevertheless, practical experiments have indicated that the method can be applied to graphs containing up to 16 vertices.
APA, Harvard, Vancouver, ISO, and other styles
4

Liu, Kai, Yi Zhang, Kai Lu, Xiaoping Wang, Xin Wang, and Guojing Tian. "MapEff: An Effective Graph Isomorphism Agorithm Based on the Discrete-Time Quantum Walk." Entropy 21, no. 6 (June 5, 2019): 569. http://dx.doi.org/10.3390/e21060569.

Full text
Abstract:
Graph isomorphism is to determine whether two graphs have the same topological structure. It plays a significant role in areas of image matching, biochemistry, and information retrieval. Quantum walk, as a novel quantum computation model, has been employed to isomorphic mapping detection to optimize the time complexity compared with a classical computation model. However, these quantum-inspired algorithms do not perform well—and even cease to work—for graphs with inherent symmetry, such as regular graphs. By analyzing the impacts of graphs symmetry on isomorphism detection, we proposed an effective graph isomorphism algorithm (MapEff) based on the discrete-time quantum walk (DTQW) to improve the accuracy of isomorphic mapping detection, especially for regular graphs. With the help of auxiliary edges, this algorithm can distinguish the symmetric nodes efficiently and, thus, deduct the qualified isomorphic mapping by rounds of selections. The experiments tested on 1585 pairs of graphs demonstrated that our algorithm has a better performance compared with other state-of-the-art algorithms.
APA, Harvard, Vancouver, ISO, and other styles
5

Zahirović, Samir, Ivica Bošnjak, and Rozália Madarász. "A study of enhanced power graphs of finite groups." Journal of Algebra and Its Applications 19, no. 04 (April 8, 2019): 2050062. http://dx.doi.org/10.1142/s0219498820500620.

Full text
Abstract:
The enhanced power graph [Formula: see text] of a group [Formula: see text] is the graph with vertex set [Formula: see text] such that two vertices [Formula: see text] and [Formula: see text] are adjacent if they are contained in the same cyclic subgroup. We prove that finite groups with isomorphic enhanced power graphs have isomorphic directed power graphs. We show that any isomorphism between undirected power graph of finite groups is an isomorphism between enhanced power graphs of these groups, and we find all finite groups [Formula: see text] for which [Formula: see text] is abelian, all finite groups [Formula: see text] with [Formula: see text] being prime power, and all finite groups [Formula: see text] with [Formula: see text] being square-free. Also, we describe enhanced power graphs of finite abelian groups. Finally, we give a characterization of finite nilpotent groups whose enhanced power graphs are perfect, and we present a sufficient condition for a finite group to have weakly perfect enhanced power graph.
APA, Harvard, Vancouver, ISO, and other styles
6

Shiau, S. Y., R. Joynt, and S. N. Coppersmith. "Physically-motivated dynamical algorithms for the graph isomorphism problem." Quantum Information and Computation 5, no. 6 (September 2005): 492–506. http://dx.doi.org/10.26421/qic5.6-7.

Full text
Abstract:
The graph isomorphism problem (GI) plays a central role in the theory of computational complexity and has importance in physics and chemistry as well \cite{kobler93,fortin96}. No polynomial-time algorithm for solving GI is known. We investigate classical and quantum physics-based polynomial-time algorithms for solving the graph isomorphism problem in which the graph structure is reflected in the behavior of a dynamical system. We show that a classical dynamical algorithm proposed by Gudkov and Nussinov \cite{gudkov02} as well as its simplest quantum generalization fail to distinguish pairs of non-isomorphic strongly regular graphs. However, by combining the algorithm of Gudkov and Nussinov with a construction proposed by Rudolph \cite{rudolph02} in which one examines a graph describing the dynamics of two particles on the original graph, we find an algorithm that successfully distinguishes all pairs of non-isomorphic strongly regular graphs that we tested with up to 29 vertices.
APA, Harvard, Vancouver, ISO, and other styles
7

Brádler, Kamil, Shmuel Friedland, Josh Izaac, Nathan Killoran, and Daiqin Su. "Graph isomorphism and Gaussian boson sampling." Special Matrices 9, no. 1 (January 1, 2021): 166–96. http://dx.doi.org/10.1515/spma-2020-0132.

Full text
Abstract:
Abstract We introduce a connection between a near-term quantum computing device, specifically a Gaussian boson sampler, and the graph isomorphism problem. We propose a scheme where graphs are encoded into quantum states of light, whose properties are then probed with photon-number-resolving detectors. We prove that the probabilities of different photon-detection events in this setup can be combined to give a complete set of graph invariants. Two graphs are isomorphic if and only if their detection probabilities are equivalent. We present additional ways that the measurement probabilities can be combined or coarse-grained to make experimental tests more amenable. We benchmark these methods with numerical simulations on the Titan supercomputer for several graph families: pairs of isospectral nonisomorphic graphs, isospectral regular graphs, and strongly regular graphs.
APA, Harvard, Vancouver, ISO, and other styles
8

He, Chaobing. "The Determination of Graph Isomorphism Using R Software." Journal of Advance Research in Mathematics And Statistics (ISSN: 2208-2409) 7, no. 11 (November 30, 2020): 01–11. http://dx.doi.org/10.53555/nnms.v7i11.945.

Full text
Abstract:
This paper considers the determination of graph isomorphism using R. After the preliminaries about graph theory is introduced systematically, the graph isomorphism determination process are studied. Then computer program for the determination of graph isomorphism is written using R. According to these R codes, the paper determines the isomorphism of three 3-regular graphs on 6 vertices and three 3-regular graphs on 8 vertices respectively, and the output proves that the R codes are very practical and effective.
APA, Harvard, Vancouver, ISO, and other styles
9

FANKHAUSER, STEFAN, KASPAR RIESEN, HORST BUNKE, and PETER DICKINSON. "SUBOPTIMAL GRAPH ISOMORPHISM USING BIPARTITE MATCHING." International Journal of Pattern Recognition and Artificial Intelligence 26, no. 06 (September 2012): 1250013. http://dx.doi.org/10.1142/s0218001412500139.

Full text
Abstract:
Graphs provide us with a flexible and powerful way to represent objects in various areas of computer science. One of the main drawbacks is, however, that many standard algorithms on graphs have a high computational complexity. The present paper considers the problem of graph isomorphism, i.e. checking two graphs for identity. A novel approach for the efficient computation of graph isomorphism is presented. The proposed algorithm is based on bipartite graph matching by means of an assignment algorithm. The algorithmic framework is suboptimal in the sense of possibly rejecting pairs of graphs without making a decision. As an advantage, however, it offers polynomial runtime. In experiments on diverse graph data sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs and otherwise returns correct results.
APA, Harvard, Vancouver, ISO, and other styles
10

Xu, Zifeng, Fucai Zhou, Yuxi Li, Jian Xu, and Qiang Wang. "Privacy-Preserving Subgraph Matching Protocol for Two Parties." International Journal of Foundations of Computer Science 30, no. 04 (June 2019): 571–88. http://dx.doi.org/10.1142/s0129054119400136.

Full text
Abstract:
Graph data structure has been widely used across many application areas, such as web data, social network, and cheminformatics. The main benefit of storing data as graphs is there exists a rich set of graph algorithms and operations that can be used to solve various computing problems, including pattern matching, data mining, and image processing. Among these graph algorithms, the subgraph isomorphism problem is one of the most fundamental algorithms that can be utilized by many higher level applications. The subgraph isomorphism problem is defined as, given two graphs [Formula: see text] and [Formula: see text], whether [Formula: see text] contains a subgraph that is isomorphic to [Formula: see text]. In this paper, we consider a special case of the subgraph isomorphism problem called the subgraph matching problem, which tests whether [Formula: see text] is a subgraph of [Formula: see text]. We propose a protocol that solve the subgraph matching problem in a privacy-preserving manner. The protocol allows two parties to jointly compute whether one graph is a subgraph of the other, while protecting the private information about the input graphs. The protocol is secure under the semi-honest setting, where each party performs the protocol faithfully.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph isomorphism"

1

Nabti, Chems Eddine. "Subgraph Isomorphism Search In Massive Graph Data." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1293/document.

Full text
Abstract:
L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recherche d'isomorphisme de sous-graphes est un problème très important impliqué dans divers domaines comme la reconnaissance de formes, l'analyse des réseaux sociaux, la biologie, etc. Il consiste à énumérer les sous-graphes d'un graphe de données qui correspondent à un graphe requête. Les solutions les plus connues de ce problème sont basées sur le retour arrière (backtracking). Elles explorent un grand espace de recherche, ce qui entraîne un coût de traitement élevé, notamment dans le cas de données massives.Pour réduire le temps et la complexité en espace mémoire dans la recherche d'isomorphisme de sous-graphes, nous proposons d'utiliser des graphes compressés. Dans notre approche, la recherche d'isomorphisme de sous-graphes est réalisée sur une représentation compressée des graphes sans les décompresser. La compression des graphes s'effectue en regroupant les sommets en super-sommets. Ce concept est connu dans la théorie des graphes par la décomposition modulaire. Il sert à générer une représentation en arbre d'un graphe qui met en évidence des groupes de sommets qui ont les mêmes voisins. Avec cette compression, nous obtenons une réduction substantielle de l'espace de recherche et par conséquent, une économie significative dans le temps de traitement.Nous proposons également une nouvelle représentation des sommets du graphe, qui simplifie le filtrage de l'espace de recherche. Ce nouveau mécanisme appelé compact neighborhood Index (CNI) encode l'information de voisinage autour d'un sommet en un seul entier. Cet encodage du voisinage réduit la complexité du temps de filtrage de cubique à quadratique. Ce qui est considérable pour les données massifs.Nous proposons également un algorithme de filtrage itératif qui repose sur les caractéristiques des CNIs pour assurer un élagage global de l'espace de recherche.Nous avons évalué nos approches sur plusieurs datasets et nous les avons comparées avec les algorithmes de l’état de l’art
Querying graph data is a fundamental problem that witnesses an increasing interest especially for massive structured data where graphs come as a promising alternative to relational databases for big data modeling. However, querying graph data is different and more complex than querying relational table-based data. The main task involved in querying graph data is subgraph isomorphism search which is an NP-complete problem. Subgraph isomorphism search, is an important problem which is involved in various domains such as pattern recognition, social network analysis, biology, etc. It consists to enumerate the subgraphs of a data graph that match a query graph. The most known solutions of this problem are backtracking-based. They explore a large search space which results in a high computational cost when we deal with massive graph data. To reduce time and memory space complexity of subgraph isomorphism search. We propose to use compressed graphs. In our approach, subgraph isomorphism search is achieved on compressed representations of graphs without decompressing them. Graph compression is performed by grouping vertices into super vertices. This concept is known, in graph theory, as modular decomposition. It is used to generate a tree representation of a graph that highlights groups of vertices that have the same neighbors. With this compression we obtain a substantial reduction of the search space and consequently a significant saving in the processing time. We also propose a novel encoding of vertices that simplifies the filtering of the search space. This new mechanism is called compact neighborhood Index (CNI). A CNI distills all the information around a vertex in a single integer. This simple neighborhood encoding reduces the time complexity of vertex filtering from cubic to quadratic which is considerable for big graphs. We propose also an iterative local global filtering algorithm that relies on the characteristics of CNIs to ensure a global pruning of the search space.We evaluated our approaches on several real-word datasets and compared them with the state of the art algorithms
APA, Harvard, Vancouver, ISO, and other styles
2

Beckman, David Eugene Preskill John P. "Investigations in quantum computing: causality and graph isomorphism /." Diss., Pasadena, Calif. : California Institute of Technology, 2004. http://resolver.caltech.edu/CaltechETD:etd-05272004-174253.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Kuhnert, Sebastian. "Space efficient algorithms for graph isomorphism and representation." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät, 2016. http://dx.doi.org/10.18452/17447.

Full text
Abstract:
Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekannt ist. Aus dieser Situation ist ein Forschungszweig erwachsen, der effiziente Isomorphiealgorithmen für eingeschränkte Graphklassen entwickelt. Der Hauptbeitrag dieser Arbeit besteht in Logspace-Algorithmen, die das Isomorphieproblem für k-Bäume, Intervallgraphen, sowie Helly- und Proper-Kreisbogengraphen lösen. Dies verbessert zuvor bekannte parallele Algorithmen und führt zu einer vollständigen Klassifikation der Komplexität dieser Probleme, da für sie auch Logspace-Härte nachgewiesen wird. Tatsächlich leisten die vorgestellten Algorithmen mehr: Im Fall der k-Bäume berechnet der Algorithmus kanonische Knotenbenennungen mit O(k log n) Platz. Eine alternative Implementation des Algorithmus kommt mit O((k+1)!n) Zeit aus – hierbei ist n die Anzahl der Knoten – und ist damit der schnellste bekannte FPT-Algorithmus für Isomorphie von k-Bäumen. Die Algorithmen für Intervall- und Kreisbogengraphen berechnen kanonische Repräsentationen – das heißt, sie weisen jedem Knoten ein Intervall (beziehungsweise einen Kreisbogen) zu, sodass diese sich genau dann schneiden, wenn die zugehörigen Knoten benachbart sind, und isomorphe Eingabegraphen das gleiche Intervallmodell (beziehungsweise Kreisbogenmodell) erhalten. Außerdem werden auch Logspace-Algorithmen angegeben, die Intervallrepräsentationen mit zusätzlichen Eigenschaften berechnen – oder erkennen, dass dies nicht möglich ist: Für die resultierenden Intervallmodelle kann gefordert werden, dass sie proper sind (also kein Intervall ein anderes enthält), dass sie unit sind (also alle Intervalle die gleiche Länge haben) oder dass die Längen der paarweisen Schnitte (und optional der einzelnen Intervalle) vorgegebenen Werten entsprechen.
The graph isomorphism problem deals with the question if two graphs have the same structure up to renaming their vertices. It is one of the few remaining natural problems for which neither a polynomial-time algorithm nor NP-hardness is known. This situation has led to a branch of research that develops efficient algorithms for special cases of the graph isomorphism problem, where the input graphs are required to be from restricted graph classes. The main contribution of this thesis comprises of logspace algorithms that solve the isomorphism problem for k-trees, interval graphs, Helly circular-arc graphs and proper circular-arc graphs. This improves previously known parallel algorithms and leads to a complete classification of the complexity of these problems, as they are also shown to be hard for logspace. In fact, these algorithms achieve more: In the case of k-trees, the algorithm computes canonical labelings in space O(k log n). An alternative implementation runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. The algorithms for interval and circular-arc graphs actually compute canonical representations, i.e., each vertex is assigned an interval (or arc) such that these intersect each other if and only if the corresponding vertices are adjacent, and isomorphic input graphs receive the same interval (or arc) model. This thesis also presents logspace algorithms that compute interval representations with additional properties, or detect that this is not possible: The resulting interval models can be required to be proper (no interval contains another), unit (all intervals have the same length), or to satisfy prescribed lengths for pairwise intersections (and possibly prescribed lengths of intervals).
APA, Harvard, Vancouver, ISO, and other styles
4

Ayeh, Eric Namuduri Kamesh. "An investigation into graph isomorphism based zero-knowledge proofs." [Denton, Tex.] : University of North Texas, 2009. http://digital.library.unt.edu/ark:/67531/metadc12076.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ayeh, Eric. "An investigation into graph isomorphism based zero-knowledge proofs." Thesis, University of North Texas, 2009. https://digital.library.unt.edu/ark:/67531/metadc12076/.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

Lester, David. "Combinator graph reduction : A congruence and its applications." Thesis, University of Oxford, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.236057.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Culp, Laura. "An Isomorphism Theorem for Graphs." VCU Scholars Compass, 2009. http://scholarscompass.vcu.edu/etd/1952.

Full text
Abstract:
In the 1970’s, L. Lovász proved that two graphs G and H are isomorphic if and only if for every graph X , the number of homomorphisms from X → G equals the number of homomorphisms from X → H . He used this result to deduce cancellation properties of the direct product of graphs. We develop a result analogous to Lovász’s theorem, but in the class of graphs without loops and with weak homomorphisms. We apply it prove a general cancellation property for the strong product of graphs.
APA, Harvard, Vancouver, ISO, and other styles
8

Meana, Richard William Piper. "Approximate Sub-Graph Isomorphism For Watermarking Finite State Machine Hardware." Scholar Commons, 2013. http://scholarcommons.usf.edu/etd/4728.

Full text
Abstract:
We present a method of mitigating theft of sequential circuit Intellectual Property hardware designs through means of watermarking. Hardware watermarking can be performed by selectively embedding a watermark in the state encoding of the Finite State Machine. This form of watermarking 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 runtime with a drawback of sub-optimal results, and finally a simulated annealing method that provides near optimal solutions with runtimes that meet our performance goals. The simulated annealing approach when applied on a ten benchmarks chosen from IWLS 93 benchmark suite, provides watermarking results with edge overhead of less than 6% on average with runtimes not exceeding five minutes.
APA, Harvard, Vancouver, ISO, and other styles
9

Balasubramanian, Suman. "On the Erdős-Sòs conjecture and the Cayley Isomorphism Problem." Diss., Mississippi State : Mississippi State University, 2009. http://library.msstate.edu/etd/show.asp?etd=etd-07102009-113145.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Tener, Greg. "ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2631.

Full text
Abstract:
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.
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Graph isomorphism"

1

Lee, B. J. Graph isomorphism. Manchester: University of Manchester, Department of Computer Science, 1996.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. The Graph Isomorphism Problem. Boston, MA: Birkhäuser Boston, 1993. http://dx.doi.org/10.1007/978-1-4612-0333-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

1955-, Schöning Uwe, and Torán Jacobo 1962-, eds. The graph isomorphism problem: Its structural complexity. Boston: Birkhäuser, 1993.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Köbler, Johannes. The Graph Isomorphism Problem: Its Structural Complexity. Boston, MA: Birkhäuser Boston, 1993.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Jones, Gareth A., Ilia Ponomarenko, and Jozef Širáň, eds. Isomorphisms, Symmetry and Computations in Algebraic Graph Theory. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-32808-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Fraïssé, Roland. La reconstruction d'une relation dans l'hypothèse forte: Isomorphie des restrictions à chaque partie stricte de la base. Montréal, Québec, Camada: Presses de l'Université Laval, 1990.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser, 2011.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Fan, Kuo-Chin. A feature-oriented label graph isomorphism algorithm and its applications. 1989.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Kobler, J., etc, Udo Schoning, and Jacobo Toran. The Graph Isomorphism Problem: Its Structural Complexity (Progress in Theoretical Computer Science). Birkhauser Verlag AG, 1993.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Kobler, J., U. Schöning, and J. Toran. The Graph Isomorphism Problem: Its Structural Complexity (Progress in Theoretical Computer Science). Birkhäuser Boston, 1993.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Graph isomorphism"

1

Valiente, Gabriel. "Graph Isomorphism." In Algorithms on Trees and Graphs, 351–97. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/978-3-662-04921-1_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

McKay, Brendan D. "Graph Isomorphism." In Encyclopedia of Algorithms, 373–76. Boston, MA: Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-30162-4_172.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

McKay, Brendan D. "Graph Isomorphism." In Encyclopedia of Algorithms, 875–79. New York, NY: Springer New York, 2016. http://dx.doi.org/10.1007/978-1-4939-2864-4_172.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Valiente, Gabriel. "Graph Isomorphism." In Texts in Computer Science, 255–85. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-81885-2_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Arvind, Vikraman, Johannes Köbler, Sebastian Kuhnert, and Yadu Vasudev. "Approximate Graph Isomorphism." In Mathematical Foundations of Computer Science 2012, 100–111. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32589-2_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Introduction." In The Graph Isomorphism Problem, 1–4. Boston, MA: Birkhäuser Boston, 1993. http://dx.doi.org/10.1007/978-1-4612-0333-9_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Preliminaries." In The Graph Isomorphism Problem, 5–10. Boston, MA: Birkhäuser Boston, 1993. http://dx.doi.org/10.1007/978-1-4612-0333-9_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Decision Problems, Search Problems, and Counting Problems." In The Graph Isomorphism Problem, 11–50. Boston, MA: Birkhäuser Boston, 1993. http://dx.doi.org/10.1007/978-1-4612-0333-9_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Quantifiers, Games, and Interactive Proofs." In The Graph Isomorphism Problem, 51–90. Boston, MA: Birkhäuser Boston, 1993. http://dx.doi.org/10.1007/978-1-4612-0333-9_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Circuits and Sparse Sets." In The Graph Isomorphism Problem, 91–116. Boston, MA: Birkhäuser Boston, 1993. http://dx.doi.org/10.1007/978-1-4612-0333-9_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Graph isomorphism"

1

Fischer, Eldar, and Arie Matsliah. "Testing graph isomorphism." In the seventeenth annual ACM-SIAM symposium. New York, New York, USA: ACM Press, 2006. http://dx.doi.org/10.1145/1109557.1109591.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Sunkari, Rajesh Pavan, and Linda C. Schmidt. "Laplace and Extended Adjacency Matrices for Isomorphism Detection of Kinematic Chains Using the Characteristic Polynomial Approach." In ASME 2005 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2005. http://dx.doi.org/10.1115/detc2005-84609.

Full text
Abstract:
The kinematic chain isomorphism problem is one of the most challenging problems facing mechanism researchers. Methods using the spectral properties, characteristic polynomial and eigenvectors, of the graph related matrices were developed in literature for isomorphism detection. Detection of isomorphism using only the spectral properties corresponds to a polynomial time isomorphism detection algorithm. However, most of the methods used are either computationally inefficient or unreliable (i.e., failing to identify non-isomorphic chains). This work establishes the reliability of using the characteristic polynomial of the Laplace matrix for isomorphism detection of a kinematic chain. The Laplace matrix of a graph is used extensively in the field of algebraic graph theory for characterizing a graph using its spectral properties. The reliability in isomorphism detection of the characteristic polynomial of the Laplace matrix was comparable with that of the adjacency matrix. However, using the characteristic polynomials of both the matrices is superior to using either method alone. In search for a single matrix whose characteristic polynomial unfailingly detects isomorphism, novel matrices called the extended adjacency matrices are developed. The reliability of the characteristic polynomials of these matrices is established. One of the proposed extended adjacency matrices is shown to be the best graph matrix for isomorphism detection using the characteristic polynomial approach.
APA, Harvard, Vancouver, ISO, and other styles
3

Ding, Huafeng, and Zhen Huang. "Isomorphism Identification of Graphs of Kinematic Chains." In ASME 2007 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2007. http://dx.doi.org/10.1115/detc2007-34148.

Full text
Abstract:
Isomorphism identification of graphs is one of the most important and challenging problems in the fields of mathematics, computer science and mechanisms. This paper attempts to solve the problem by finding a unique representation of graphs. First, the perimeter loop of a graph is identified from all the loops of the graph obtained through a new algorithm. From the perimeter loop a corresponding perimeter graph is derived, which renders the forms of the graph canonical. Then, by relabelling the perimeter graph, the canonical perimeter graph is obtained, reducing the adjacency matrices of a graph from hundreds of thousands to several or even just one. On the basis of canonical adjacency matrix set, the unique representation of the graph, the characteristic adjacency matrix, is obtained. In such a way, isomorphism identification, sketching, and establishment of the database of common graphs, including the graphs of kinematic chains, all become easy to realize. Computational complexity analysis shows that, in the field of kinematic chains the approach is much more efficient than McKay’s algorithm which is considered the fastest so far. Our algorithm remains efficient even when the links of kinematic chains increase into the thirties.
APA, Harvard, Vancouver, ISO, and other styles
4

BABAI, LÁSZLÓ. "GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM." In International Congress of Mathematicians 2018. WORLD SCIENTIFIC, 2019. http://dx.doi.org/10.1142/9789813272880_0183.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Hsu, Cheng-Ho, and Kin-Tak Lam. "A Method for the Identification of Displacement Isomorphism of Planetary Gear Trains." In ASME 1992 Design Technical Conferences. American Society of Mechanical Engineers, 1992. http://dx.doi.org/10.1115/detc1992-0419.

Full text
Abstract:
Abstract The purpose of this paper is to present an efficient method for the identification of the displacement isomorphism of planetary gear trains. For every planetary gear train, the kinematic structure is characterized by its displacement graph and rotation graph. A mathematical representation, called the Structural Code, is introduced to represent the topological structure of the displacement graph and rotation graph of a planetary gear train. Based on the Structural Codes of displacement graphs and rotation graphs, the linear and rotational displacement isomorphism of planetary gear trains can be identified in an unambiguous way. Finally, an interactive computer program is developed for the automatic identification of the displacement isomorphism of planetary gear trains.
APA, Harvard, Vancouver, ISO, and other styles
6

Zhao, Wenting, Yuan Fang, Zhen Cui, Tong Zhang, and Jian Yang. "Graph Deformer Network." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/227.

Full text
Abstract:
Convolution learning on graphs draws increasing attention recently due to its potential applications to a large amount of irregular data. Most graph convolution methods leverage the plain summation/average aggregation to avoid the discrepancy of responses from isomorphic graphs. However, such an extreme collapsing way would result in a structural loss and signal entanglement of nodes, which further cause the degradation of the learning ability. In this paper, we propose a simple yet effective Graph Deformer Network (GDN) to fulfill anisotropic convolution filtering on graphs, analogous to the standard convolution operation on images. Local neighborhood subgraphs (acting like receptive fields) with different structures are deformed into a unified virtual space, coordinated by several anchor nodes. In the deformation process, we transfer components of nodes therein into affinitive anchors by learning their correlations, and build a multi-granularity feature space calibrated with anchors. Anisotropic convolutional kernels can be further performed over the anchor-coordinated space to well encode local variations of receptive fields. By parameterizing anchors and stacking coarsening layers, we build a graph deformer network in an end-to-end fashion. Theoretical analysis indicates its connection to previous work and shows the promising property of graph isomorphism testing. Extensive experiments on widely-used datasets validate the effectiveness of GDN in graph and node classifications.
APA, Harvard, Vancouver, ISO, and other styles
7

Kraiczy, Sonja, and Ciaran McCreesh. "Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/193.

Full text
Abstract:
Graph homomorphism problems involve finding adjacency-preserving mappings between two given graphs. Although theoretically hard, these problems can often be solved in practice using constraint programming algorithms. We show how techniques from the state-of-the-art in subgraph isomorphism solving can be applied to broader graph homomorphism problems, and introduce a new form of filtering based upon clique-finding. We demonstrate empirically that this filtering is effective for the locally injective graph homomorphism and subgraph isomorphism problems, and gives the first practical constraint programming approach to finding general graph homomorphisms.
APA, Harvard, Vancouver, ISO, and other styles
8

Jongsma, T. J., and W. Zhang. "An Efficient Algorithm for Finding Optimum Code Under the Condition of Incident Degree." In ASME 1992 Design Technical Conferences. American Society of Mechanical Engineers, 1992. http://dx.doi.org/10.1115/detc1992-0409.

Full text
Abstract:
Abstract This paper deals with the identification of kinematic chains. A kinematic chain can be represented by a weighed graph. The identification of kinematic chains is thereby transformed into the isomorphism problem of graph. When a computer program has to detect isomorphism between two graphs, the first step is to set up the corresponding connectivity matrices for each graph, which are adjacency matrices when considering adjacent vertices and the weighed edges between them. Because these adjacency matrices are dependent of the initial labelling, one can not conclude that the graphs differ when these matrices differ. The isomorphism problem needs an algorithm which is independent of the initial labelling. This paper provides such an algorithm.
APA, Harvard, Vancouver, ISO, and other styles
9

Al-Zabi, Bilal Radi A'Ggel, Andriy Kernytskyy, Mykhaylo Lobur, and Serhiy Tkatchenko. "On graph isomorphism determining problem." In 2008 International Conference on Perspective Technologies and Methods in MEMS Design (MEMSTECH). IEEE, 2008. http://dx.doi.org/10.1109/memstech.2008.4558745.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Samsi, Siddharth, Vijay Gadepally, Michael Hurley, Michael Jones, Edward Kao, Sanjeev Mohindra, Paul Monticciolo, et al. "Static graph challenge: Subgraph isomorphism." In 2017 IEEE High-Performance Extreme Computing Conference (HPEC). IEEE, 2017. http://dx.doi.org/10.1109/hpec.2017.8091039.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Graph isomorphism"

1

Gross, Jonathan L. Topological Representation of Graph Isomorphism Types. Fort Belvoir, VA: Defense Technical Information Center, November 1991. http://dx.doi.org/10.21236/ada243528.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ja'Ja, Joseph, and S. R. Kosaraju. Parallel Algorithms for Planar Graph. Isomorphism and Related Problems. Fort Belvoir, VA: Defense Technical Information Center, January 1986. http://dx.doi.org/10.21236/ada444434.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph isomorphism' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography