Log in

Relevant bibliographies by topics / GRAPH ISOMORPHISM PROBLEM

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'GRAPH ISOMORPHISM PROBLEM'

Author: Grafiati

Published: 4 June 2021

Last updated: 18 May 2023

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 PROBLEM.'

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 PROBLEM"

1

RAJASEKARAN, SANGUTHEVAR, and VAMSI KUNDETI. "SPECTRUM BASED TECHNIQUES FOR GRAPH ISOMORPHISM." International Journal of Foundations of Computer Science 20, no. 03 (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 prov

APA, Harvard, Vancouver, ISO, and other styles

2

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

APA, Harvard, Vancouver, ISO, and other styles

3

Zemlyachenko, V. N., N. M. Korneenko, and R. I. Tyshkevich. "Graph isomorphism problem." Journal of Soviet Mathematics 29, no. 4 (1985): 1426–81. http://dx.doi.org/10.1007/bf02104746.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Rybalov, A. N. "ON GENERIC COMPLEXITY OF THE ISOMORPHISM PROBLEM FOR FINITE SEMIGROUPS." Prikladnaya Diskretnaya Matematika, no. 51 (2021): 120–28. http://dx.doi.org/10.17223/20710410/51/6.

Full text

Abstract:

Generic-case approach to algorithmic problems was suggested by A. Miasnikov, V. Kapovich, P. Schupp, and V. Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper, we study the generic complexity of the isomorphism problem for finite semigroups. In this problem, for any two semigroups of the same order, given by their multiplication tables, it is required to determine whether they are isomorphic. V. Zemlyachenko, N. Korneenko, and R. Tyshkevich in 1982 proved that the graph isomorphism problem polynomially

APA, Harvard, Vancouver, ISO, and other styles

5

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

APA, Harvard, Vancouver, ISO, and other styles

6

Grohe, Martin, and Pascal Schweitzer. "The graph isomorphism problem." Communications of the ACM 63, no. 11 (2020): 128–34. http://dx.doi.org/10.1145/3372123.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Liu, X., and D. J. Klein. "The graph isomorphism problem." Journal of Computational Chemistry 12, no. 10 (1991): 1243–51. http://dx.doi.org/10.1002/jcc.540121012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Bouyukliev, Iliya, and Mariya Dzhumalieva-Stoeva. "Representing Equivalence Problems for Combinatorial Objects." Serdica Journal of Computing 8, no. 4 (2015): 327–54. http://dx.doi.org/10.55630/sjc.2014.8.327-354.

Full text

Abstract:

Methods for representing equivalence problems of various combinatorial objectsas graphs or binary matrices are considered. Such representations can be used for isomorphism testing in classification or generation algorithms. Often it is easier to consider a graph or a binary matrix isomorphism problem than to implement heavy algorithms depending especially on particular combinatorialobjects. Moreover, there already exist well tested algorithms for the graph isomorphismproblem (nauty) and the binary matrix isomorphism problem as well (Q-Extension).ACM Computing Classification System (1998): F.2.

APA, Harvard, Vancouver, ISO, and other styles

9

Ponomarenko, I. N. "Graph algebras and the graph isomorphism problem." Applicable Algebra in Engineering, Communication and Computing 5, no. 5 (1994): 277–86. http://dx.doi.org/10.1007/bf01225642.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Brádler, Kamil, Shmuel Friedland, Josh Izaac, Nathan Killoran, and Daiqin Su. "Graph isomorphism and Gaussian boson sampling." Special Matrices 9, no. 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 b

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "GRAPH ISOMORPHISM PROBLEM"

1

Balasubramanian, Suman. "On the Erdős-Sò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

2

Dona, Daniele [Verfasser]. "Growth in finite groups and the Graph Isomorphism Problem / Daniele Dona." Göttingen : Niedersächsische Staats- und Universitätsbibliothek Göttingen, 2020. http://d-nb.info/1216330662/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Tamburini, Caterina. "The isomorphism problem for directed acyclic graphs: an application to multivector fields." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/15793/.

Full text

Abstract:

This thesis is based on a project developed by a group of researchers at the Faculty of Mathematics and Computer Science at the Jagiellonian University of Krakow. They study sampled dynamics using combinatorial multivector fields. Applying a decomposition into strongly connected components, it is possible to create a directed acyclic graph, called Morse graph, which is a description of the multivector field's global dynamics. Therefore the purpose of this thesis is to compare directed acyclic graphs. In the first chapter we describe the creation process of a Morse graph and an algorithm to stu

APA, Harvard, Vancouver, ISO, and other styles

4

Stejskal, Roman. "Zjišťování izomorfizmu grafů v databázi." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-236007.

Full text

Abstract:

This project introduces history and basic notions of the graph theory. It describes graph theory problems, possible graph representations and practical graph management in databases. Aims to subgraph and graph isomorphism. It describes possible ways to find graph isomorphism and chosen algorithms for subgraph and graph isomorphism. The experimental part aims to comparing two implemented algorithms. These are Ullmann and VF2 algorithm. Also searches difference between graphs stored in memory and graphs stored in database.

APA, Harvard, Vancouver, ISO, and other styles

5

Wiebking, Daniel [Verfasser], Martin [Akademischer Betreuer] Grohe, Pascal [Akademischer Betreuer] Schweitzer, and Jacobo [Akademischer Betreuer] Torán. "A decomposition-compatible canonization framework for the graph isomorphism problem / Daniel Wiebking ; Martin Grohe, Pascal Schweitzer, Jacobo Torán." Aachen : Universitätsbibliothek der RWTH Aachen, 2021. http://d-nb.info/1240480377/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Neuen, Daniel [Verfasser], Martin [Akademischer Betreuer] Grohe, Pascal [Akademischer Betreuer] Schweitzer, and László [Akademischer Betreuer] Babai. "The power of algorithmic approaches to the graph isomorphism problem / Daniel Neuen ; Martin Grohe, Pascal Schweitzer, László Babai." Aachen : Universitätsbibliothek der RWTH Aachen, 2019. http://d-nb.info/1216040826/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Santos, Philippe Leal Freire dos. "Teoria Espectral de Grafos aplicada ao problema de Isomorfismo de Grafos." Universidade Federal do Espírito Santo, 2010. http://repositorio.ufes.br/handle/10/6388.

Full text

Abstract:

Made available in DSpace on 2016-12-23T14:33:41Z (GMT). No. of bitstreams: 1 Dissertacao de Philippe Leal Freire dos Santos.pdf: 1222437 bytes, checksum: 0b5ab3d6e8b9f4b4640e53168b2d042d (MD5) Previous issue date: 2010-08-23<br>In this work we investigated the use of concepts from Spectral Graph Theory (SGT) to support the construction of algorithms that solve the Graph Isomorphism Problem (GIP). Three theoretical results which consider information from the spectrum of the graphs and from the eigenvector centralities were presented. Furthermore, an algorithm for detection of graph isomorphis

APA, Harvard, Vancouver, ISO, and other styles

8

Ribeyre, Corentin. "Méthodes d’analyse supervisée pour l’interface syntaxe-sémantique : de la réécriture de graphes à l’analyse par transitions." Sorbonne Paris Cité, 2016. http://www.theses.fr/2016USPCC119.

Full text

Abstract:

Aujourd'hui, le volume de données textuelles disponibles est colossal. Ces données représentent des informations inestimables impossibles à traiter manuellement. De fait, il est essentiel d'utiliser des techniques de Traitement Automatique des Langues pour extraire les informations saillantes et comprendre le sens sous-jacent. Cette thèse s'inscrit dans cette perspective et proposent des ressources, des modèles et des méthodes pour permettre : (i) l'annotation automatique de corpus à l'interface entre la syntaxe et la sémantique afin d'en extraire la structure argumentale (ii) l'exploitation d

APA, Harvard, Vancouver, ISO, and other styles

9

Colledan, Andrea. "On the Hidden Subgroup Problem as a Pivot in Quantum Complexity Theory." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16112/.

Full text

Abstract:

Quantum computing has opened the way to new algorithms that can efficiently solve problems that have always been deemed intractable. However, since quantum algorithms are hard to design, the necessity to find a generalization of these problems arises. Such necessity is satisfied by the hidden subgroup problem (HSP), an abstract problem of group theory which successfully generalizes a large number of intractable problems. The HSP plays a significant role in quantum complexity theory, as efficient algorithms that solve it can be employed to efficiently solve other valuable problems, such as inte

APA, Harvard, Vancouver, ISO, and other styles

10

Rodrigues, Edilson José. "Um algoritmo para o Problema do Isomorfismo de Grafos." reponame:Repositório Institucional da UFABC, 2014.

Find full text

Abstract:

Orientador: Prof. Dr. Daniel Morgato Martin<br>Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciências da Computação, 2014.<br>Neste trabalho estudamos o Problema do Isomorfismo de Grafos e a sua complexidade para resolvê-lo. Nossa principal contribuição é a proposta de um algoritmo para o caso geral do Problema, baseado no particionamento do conjunto de vértices e em emparelhamentos perfeitos de grafos bipartidos. Estudamos também o algoritmo de Brendan McKay, que é o mais rápido algoritmo para o Problema do Isomorfismo de Grafos conhecido. Ao final, implem

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "GRAPH ISOMORPHISM PROBLEM"

1

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

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

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

1955-, Schöning Uwe, and Torán Jacobo 1962-, eds. The graph isomorphism problem: Its structural complexity. Birkhäuser, 1993.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

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

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

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

6

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 PROBLEM"

1

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Decision Problems, Search Problems, and Counting Problems." In The Graph Isomorphism Problem. 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

2

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Introduction." In The Graph Isomorphism Problem. 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

3

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Preliminaries." In The Graph Isomorphism Problem. 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

4

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Quantifiers, Games, and Interactive Proofs." In The Graph Isomorphism Problem. 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

5

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Circuits and Sparse Sets." In The Graph Isomorphism Problem. 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

6

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

de Ridder, H. N., and N. de Ridder. "The Subgraph Isomorphism Problem on a Class of Hyperedge Replacement Languages." In Graph Transformation. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-09108-2_13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ghosh, Sumanta, and Piyush P. Kurur. "Permutation Groups and the Graph Isomorphism Problem." In Perspectives in Computational Complexity. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-05446-9_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

McCreesh, Ciaran, Patrick Prosser, and James Trimble. "The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants." In Graph Transformation. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-51372-6_19.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Grohe, Martin. "Logical and Structural Approaches to the Graph Isomorphism Problem." In Mathematical Foundations of Computer Science 2013. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40313-2_4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "GRAPH ISOMORPHISM PROBLEM"

1

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

2

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

3

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 charac

APA, Harvard, Vancouver, ISO, and other styles

4

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 grap

APA, Harvard, Vancouver, ISO, and other styles

5

Kirichkov, A. E. "Quantum search algorithm for graph isomorphism problem." In Quantum Informatics 2007. SPIE, 2008. http://dx.doi.org/10.1117/12.801901.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Benreguia, Badreddine, and Hamamache Kheddouci. "A consistency rule for graph isomorphism problem." In the 27th Annual ACM Symposium. ACM Press, 2012. http://dx.doi.org/10.1145/2245276.2245453.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

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

APA, Harvard, Vancouver, ISO, and other styles

8

Grohe, Martin. "Structural and Logical Approaches to the Graph Isomorphism Problem." In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2012. http://dx.doi.org/10.1137/1.9781611973099.16.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Li, Guo, Guan Rong, Li Kenli, and Li Renfa. "Fast Parallel Molecular Algorithms for DNA-Based Computation: Graph Isomorphism Problem." In 2009 2nd International Conference on Biomedical Engineering and Informatics. IEEE, 2009. http://dx.doi.org/10.1109/bmei.2009.5302914.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Morris, Christopher, Matthias Fey, and Nils Kriege. "The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/618.

Full text

Abstract:

In recent years, algorithms and neural architectures based on the Weisfeiler-Leman algorithm, a well-known heuristic for the graph isomorphism problem, emerged as a powerful tool for (supervised) machine learning with graphs and relational data. Here, we give a comprehensive overview of the algorithm's use in a machine learning setting. We discuss the theoretical background, show how to use it for supervised graph- and node classification, discuss recent extensions, and its connection to neural architectures. Moreover, we give an overview of current applications and future directions to stimul

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "GRAPH ISOMORPHISM PROBLEM"

1

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

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