Log in

Relevant bibliographies by topics / Graph isomorphism / Journal articles

To see the other types of publications on this topic, follow the link: Graph isomorphism.

Journal articles 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 top 50 journal articles for your research 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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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

11

TAKAOKA, Asahi. "Graph Isomorphism Completeness for Trapezoid Graphs." IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A, no. 8 (2015): 1838–40. http://dx.doi.org/10.1587/transfun.e98.a.1838.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

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 reduces to this problem. The graph isomorphism problem is a well-known algorithmic problem that has been actively studied since the 1970s, and for which polynomial algorithms are still unknown. So from a computational point of view the studied problem is no simpler than the graph isomorphism problem. We present a generic polynomial algorithm for the isomorphism problem of finite semigroups. It is based on the characterization of almost all finite semigroups as 3-nilpotent semigroups of a special form, established by D. Kleitman, B. Rothschild, and J. Spencer, as well as the Bollobas polynomial algorithm, which solves the isomorphism problem for almost all strongly sparse graphs.

APA, Harvard, Vancouver, ISO, and other styles

13

Fischer, Eldar, and Arie Matsliah. "Testing Graph Isomorphism." SIAM Journal on Computing 38, no. 1 (January 2008): 207–25. http://dx.doi.org/10.1137/070680795.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Sun, Wei, Ronghe Li, Jianyi Kong, and Anming Li. "A new method for isomorphism identification of planetary gear trains." Mechanical Sciences 12, no. 1 (February 18, 2021): 193–202. http://dx.doi.org/10.5194/ms-12-193-2021.

Full text

Abstract:

Abstract. Planetary gear trains (PGTs) are widely used in machinery such as vehicles, pulley blocks, wrist watches, machine tools, and robots. During the process of structural synthesis of PGTs using graph theory, isomorphism identification of graphs is an important and complicated problem. The reliability of the isomorphism detection method directly determines the accuracy of the synthesis result. In this paper, a novel isomorphism identification method for PGTs is proposed. First, a new weighted adjacent matrix is presented to describe the topological graph of PGTs, which has is unique in describing the structure of PGTs. Then, the weighted distance matrix is proposed and the sum of the matrix is obtained, which can determine whether the planetary gear trains is isomorphic or not. Eventually, the examples demonstrate that this new method can be accurately and effectively performed.

APA, Harvard, Vancouver, ISO, and other styles

16

LING, BO, CI XUAN WU, and BEN GONG LOU. "PENTAVALENT SYMMETRIC GRAPHS OF ORDER." Bulletin of the Australian Mathematical Society 90, no. 3 (August 27, 2014): 353–62. http://dx.doi.org/10.1017/s0004972714000616.

Full text

Abstract:

AbstractA complete classification is given of pentavalent symmetric graphs of order$30p$, where$p\ge 5$is a prime. It is proved that such a graph${\Gamma }$exists if and only if$p=13$and, up to isomorphism, there is only one such graph. Furthermore,${\Gamma }$is isomorphic to$\mathcal{C}_{390}$, a coset graph of PSL(2, 25) with${\sf Aut}\, {\Gamma }=\mbox{PSL(2, 25)}$, and${\Gamma }$is 2-regular. The classification involves a new 2-regular pentavalent graph construction with square-free order.

APA, Harvard, Vancouver, ISO, and other styles

17

Carlsen, Toke Meier, and James Rout. "Diagonal-preserving graded isomorphisms of Steinberg algebras." Communications in Contemporary Mathematics 20, no. 06 (August 27, 2018): 1750064. http://dx.doi.org/10.1142/s021919971750064x.

Full text

Abstract:

We study Steinberg algebras constructed from ample Hausdorff groupoids over commutative integral domains with identity. We reconstruct (graded) groupoids from (graded) Steinberg algebras and use this to characterize when there is a diagonal-preserving (graded) isomorphism between two (graded) Steinberg algebras. We apply this characterization to groupoids of directed graphs in order to study diagonal-preserving (graded) isomorphisms of Leavitt path algebras and ∗-isomorphisms of graph [Formula: see text]-algebras.

APA, Harvard, Vancouver, ISO, and other styles

18

Aflalo, Yonathan, Alexander Bronstein, and Ron Kimmel. "On convex relaxation of graph isomorphism." Proceedings of the National Academy of Sciences 112, no. 10 (February 23, 2015): 2942–47. http://dx.doi.org/10.1073/pnas.1401651112.

Full text

Abstract:

We consider the problem of exact and inexact matching of weighted undirected graphs, in which a bijective correspondence is sought to minimize a quadratic weight disagreement. This computationally challenging problem is often relaxed as a convex quadratic program, in which the space of permutations is replaced by the space of doubly stochastic matrices. However, the applicability of such a relaxation is poorly understood. We define a broad class of friendly graphs characterized by an easily verifiable spectral property. We prove that for friendly graphs, the convex relaxation is guaranteed to find the exact isomorphism or certify its inexistence. This result is further extended to approximately isomorphic graphs, for which we develop an explicit bound on the amount of weight disagreement under which the relaxation is guaranteed to find the globally optimal approximate isomorphism. We also show that in many cases, the graph matching problem can be further harmlessly relaxed to a convex quadratic program with only n separable linear equality constraints, which is substantially more efficient than the standard relaxation involving 2n equality and n2 inequality constraints. Finally, we show that our results are still valid for unfriendly graphs if additional information in the form of seeds or attributes is allowed, with the latter satisfying an easy to verify spectral characteristic.

APA, Harvard, Vancouver, ISO, and other styles

19

Boldi, Paolo, Violetta Lonati, Massimo Santini, and Sebastiano Vigna. "Graph fibrations, graph isomorphism, and PageRank." RAIRO - Theoretical Informatics and Applications 40, no. 2 (April 2006): 227–53. http://dx.doi.org/10.1051/ita:2006004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Zivković, Tomislav P. "On graph isomorphism and graph automorphism." Journal of Mathematical Chemistry 8, no. 1 (December 1991): 19–37. http://dx.doi.org/10.1007/bf01166921.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Bagga, Jay. "Old and new generalizations of line graphs." International Journal of Mathematics and Mathematical Sciences 2004, no. 29 (2004): 1509–21. http://dx.doi.org/10.1155/s0161171204310094.

Full text

Abstract:

Line graphs have been studied for over seventy years. In 1932, H. Whitney showed that for connected graphs, edge-isomorphism implies isomorphism except forK3andK1,3. The line graph transformation is one of the most widely studied of all graph transformations. In its long history, the concept has been rediscovered several times, with different names such as derived graph, interchange graph, and edge-to-vertex dual. Line graphs can also be considered as intersection graphs. Several variations and generalizations of line graphs have been proposed and studied. These include the concepts of total graphs, path graphs, and others. In this brief survey we describe these and some more recent generalizations and extensions including super line graphs and triangle graphs.

APA, Harvard, Vancouver, ISO, and other styles

22

Flippen, Christopher, Allison H. Moore, and Essak Seddiq. "Quotients of the Gordian and H(2)-Gordian graphs." Journal of Knot Theory and Its Ramifications 30, no. 05 (April 2021): 2150037. http://dx.doi.org/10.1142/s0218216521500371.

Full text

Abstract:

The Gordian graph and H(2)-Gordian graphs of knots are abstract graphs whose vertex sets represent isotopy classes of unoriented knots, and whose edge sets record whether pairs of knots are related by crossing changes or H(2)-moves, respectively. We investigate quotients of these graphs under equivalence relations defined by several knot invariants including the determinant, the span of the Jones polynomial, and an invariant related to tricolorability. We show, in all cases considered, that the quotient graphs are Gromov hyperbolic. We then prove a collection of results about the graph isomorphism type of the quotient graphs. In particular, we find that the H(2)-Gordian graph of links modulo the relation induced by the span of the Jones polynomial is isomorphic with the complete graph on infinitely many vertices.

APA, Harvard, Vancouver, ISO, and other styles

23

Duong, Chi Thang, Trung Dung Hoang, Hongzhi Yin, Matthias Weidlich, Quoc Viet Hung Nguyen, and Karl Aberer. "Efficient streaming subgraph isomorphism with graph neural networks." Proceedings of the VLDB Endowment 14, no. 5 (January 2021): 730–42. http://dx.doi.org/10.14778/3446095.3446097.

Full text

Abstract:

Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do not scale to a dynamic setting of a continuous stream of queries. In this paper, we address the scalability challenges induced by a stream of subgraph isomorphism queries by caching and re-use of previous results. We first present a novel subgraph index based on graph embeddings that serves as the foundation for efficient stream processing. It enables not only effective caching and re-use of results, but also speeds-up traditional algorithms for subgraph isomorphism in case of cache misses. Moreover, we propose cache management policies that incorporate notions of reusability of query results. Experiments using real-world datasets demonstrate the effectiveness of our approach in handling isomorphic subgraph search for streams of queries.

APA, Harvard, Vancouver, ISO, and other styles

24

Ma, Ming Yue, and Xiang Yang Xu. "A Novel Algorithm for Enumeration of the Planetary Gear Train Based on Graph Theory." Advanced Materials Research 199-200 (February 2011): 392–99. http://dx.doi.org/10.4028/www.scientific.net/amr.199-200.392.

Full text

Abstract:

As well known, graph theory is a powerful tool for mechanism design. The enumeration of planet gear trains can be converted the synthesis of graphs while a planetary gear train is converted to a graph. During the enumeration of graphs, the problem of isomorphism should be solved. This paper proposes a novel algorithm used to generate non-isomorphism graphs and thereby omits the part of isomorphism detection. The vertex characteristic is firstly defined in this paper that is the core of the enumeration algorithm. This paper also gives an example of the application for the algorithm.

APA, Harvard, Vancouver, ISO, and other styles

25

Grohe, Martin, and Daniel Neuen. "Isomorphism, canonization, and definability for graphs of bounded rank width." Communications of the ACM 64, no. 5 (May 2021): 98–105. http://dx.doi.org/10.1145/3453943.

Full text

Abstract:

We investigate the interplay between the graph isomorphism problem, logical definability, and structural graph theory on a rich family of dense graph classes: graph classes of bounded rank width. We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3 k + 4) is a complete isomorphism test for the class of all graphs of rank width at most k. A consequence of our result is the first polynomial time canonization algorithm for graphs of bounded rank width. Our second main result addresses an open problem in descriptive complexity theory: we show that fixed-point logic with counting expresses precisely the polynomial time properties of graphs of bounded rank width.

APA, Harvard, Vancouver, ISO, and other styles

26

Torán, Jacobo. "Reductions to Graph Isomorphism." Theory of Computing Systems 47, no. 1 (December 2, 2008): 288–99. http://dx.doi.org/10.1007/s00224-008-9159-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

McKay, Brendan D., and Adolfo Piperno. "Practical graph isomorphism, II." Journal of Symbolic Computation 60 (January 2014): 94–112. http://dx.doi.org/10.1016/j.jsc.2013.09.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Onn, Shmuel. "Two graph isomorphism polytopes." Discrete Mathematics 309, no. 9 (May 2009): 2934–36. http://dx.doi.org/10.1016/j.disc.2008.07.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Imrich, W., and G. Sabidussi. "Focality and graph isomorphism." Discrete Mathematics 81, no. 3 (May 1990): 237–45. http://dx.doi.org/10.1016/0012-365x(90)90063-n.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Czajka, Tomek, and Gopal Pandurangan. "Improved random graph isomorphism." Journal of Discrete Algorithms 6, no. 1 (March 2008): 85–92. http://dx.doi.org/10.1016/j.jda.2007.01.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Prasad Raju Pathapati, V. V. N. R., and A. C. Rao. "A New Technique Based on Loops to Investigate Displacement Isomorphism in Planetary Gear Trains." Journal of Mechanical Design 124, no. 4 (November 26, 2002): 662–75. http://dx.doi.org/10.1115/1.1503373.

Full text

Abstract:

The most important step in the structural synthesis of planetary gear trains (PGTs) requires the identification of isomorphism (rotational as well as displacement) between the graphs which represent the kinematic structure of planetary gear train. Previously used methods for identifying graph isomorphism yielded incorrect results. Literature review in this area shows there is inconsistency in results from six link, one degree-of-freedom onwards. The purpose of this paper is to present an efficient methodology through the use of Loop concept and Hamming number concept to detect displacement and rotational isomorphism in PGTs in an unambiguous way. New invariants for rotational graphs and displacement graphs called geared chain hamming strings and geared chain loop hamming strings are developed respectively to identify rotational and displacement isomorphism. This paper also presents a procedure to redraw conventional graph representation that not only clarifies the kinematic structure of a PGT but also averts the problem of pseudo isomorphism. Finally a thorough analysis of existing methods is carried out using the proposed technique and the results in the category of six links one degree-of-freedom are established and an Atlas comprises of graph representations in conventional form as well as in new form is presented.

APA, Harvard, Vancouver, ISO, and other styles

35

Hazlewood, Robert, Iain Raeburn, Aidan Sims, and Samuel B. G. Webster. "Remarks on some fundamental results about higher-rank graphs and their C*-algebras." Proceedings of the Edinburgh Mathematical Society 56, no. 2 (April 30, 2013): 575–97. http://dx.doi.org/10.1017/s0013091512000338.

Full text

Abstract:

AbstractResults of Fowler and Sims show that every k-graph is completely determined by its k-coloured skeleton and collection of commuting squares. Here we give an explicit description of the k-graph associated with a given skeleton and collection of squares and show that two k-graphs are isomorphic if and only if there is an isomorphism of their skeletons which preserves commuting squares. We use this to prove directly that each k-graph Λ is isomorphic to the quotient of the path category of its skeleton by the equivalence relation determined by the commuting squares, and show that this extends to a homeomorphism of infinite-path spaces when the k-graph is row finite with no sources. We conclude with a short direct proof of the characterization, originally due to Robertson and Sims, of simplicity of the C*-algebra of a row-finite k-graph with no sources.

APA, Harvard, Vancouver, ISO, and other styles

36

He and, P. R., W. J. Zhang, Q. Li and, and F. X. Wu. "A New Method for Detection of Graph Isomorphism Based on the Quadratic Form." Journal of Mechanical Design 125, no. 3 (September 1, 2003): 640–42. http://dx.doi.org/10.1115/1.1564574.

Full text

Abstract:

This paper proposes a new method for detection of graph isomorphism using the concept of quadratic form. Graphs/kinematic chains are represented first by quadratic form, and the comparison of two graphs is thus reduced to the comparison of two quadratic form expressions. If both the lengths and the directions of the semiaxes of quadric surfaces, which are characterized by the eigenvalues and eigenvectors, are the same, the associated graphs/kinematic chains are isomorphic. An algorithm is developed based on this idea, and tested for the counter-examples known to other methods.

APA, Harvard, Vancouver, ISO, and other styles

37

Aigner, Martin, and Eberhard Triesch. "Reconstructing a Graph from its Neighborhood Lists." Combinatorics, Probability and Computing 2, no. 2 (June 1993): 103–13. http://dx.doi.org/10.1017/s0963548300000535.

Full text

Abstract:

Associate to a finite labeled graph G(V, E) its multiset of neighborhoods (G) = {N(υ): υ ∈ V}. We discuss the question of when a list is realizable by a graph, and to what extent G is determined by (G). The main results are: the decision problem is NP-complete; for bipartite graphs the decision problem is polynomially equivalent to Graph Isomorphism; forests G are determined up to isomorphism by (G); and if G is connected bipartite and (H) = (G), then H is completely described.

APA, Harvard, Vancouver, ISO, and other styles

38

Douar, Brahim, Chiraz Latiri, Michel Liquiere, and Yahya Slimani. "A Projection Bias in Frequent Subgraph Mining Can Make a Difference." International Journal on Artificial Intelligence Tools 23, no. 05 (October 2014): 1450005. http://dx.doi.org/10.1142/s0218213014500055.

Full text

Abstract:

The aim of the frequent subgraph mining task is to find frequently occurring subgraphs in a large graph database. However, this task is a thriving challenge, as graph and subgraph isomorphisms play a key role throughout the computations. Since subgraph isomorphism testing is a hard problem, subgraph miners are exponential in runtime. To alleviate the complexity issue, we propose to introduce a bias in the projection operator and instead of using the costly subgraph isomorphism projection, one can use a polynomial projection having a semantically-valid structural interpretation. This paper presents a new projection operator for graphs named AC-projection, which exhibits nice theoretical complexity properties. We study the size of the search space as well as some practical properties of the projection operator. We also introduce a novel breadth-first algorithm for frequent AC-reduced subgraphs mining. Then, we prove experimentally that we can achieve an important performance gain (polynomial complexity projection) without or with non-significant loss of discovered patterns in terms of quality.

APA, Harvard, Vancouver, ISO, and other styles

39

Hou, Ai Min, Chuan Fu Hu, and Zhi Feng Hao. "A General Vertex Partition Refinement Algorithm for Graph Isomorphism." Advanced Materials Research 760-762 (September 2013): 1919–24. http://dx.doi.org/10.4028/www.scientific.net/amr.760-762.1919.

Full text

Abstract:

A general depth-first backtracking algorithm for graph isomorphism with the vertex partition and refinement technique is presented in this paper. The time complexity of this nondeterministic polynomial algorithm is O(nα+3) where nα is the number of backtracking points and (h-1)/2α (h+1)/2 for h=logn in the worst cases. The tests on many types of graphs validated the efficiency of this algorithm for graph isomorphism.

APA, Harvard, Vancouver, ISO, and other styles

40

SØRENSEN, ADAM P. W. "Geometric classification of simple graph algebras." Ergodic Theory and Dynamical Systems 33, no. 4 (July 5, 2012): 1199–220. http://dx.doi.org/10.1017/s0143385712000260.

Full text

Abstract:

AbstractInspired by Franks’ classification of irreducible shifts of finite type, we provide a short list of allowed moves on graphs that preserve the stable isomorphism class of the associated $C^*$-algebras. We show that if two graphs have stably isomorphic and simple unital algebras then we can use these moves to transform one into the other.

APA, Harvard, Vancouver, ISO, and other styles

41

Akram, Muhammad, Jawaria Dar, and Adeel Farooq. "Planar Graphs under Pythagorean Fuzzy Environment." Mathematics 6, no. 12 (November 25, 2018): 278. http://dx.doi.org/10.3390/math6120278.

Full text

Abstract:

Graph theory plays a substantial role in structuring and designing many problems. A number of structural designs with crossings can be found in real world scenarios. To model the vagueness and uncertainty in graphical network problems, many extensions of graph theoretical ideas are introduced. To deal with such uncertain situations, the present paper proposes the concept of Pythagorean fuzzy multigraphs and Pythagorean fuzzy planar graphs with some of their eminent characteristics by investigating Pythagorean fuzzy planarity value with strong, weak and considerable edges. A close association is developed between Pythagorean fuzzy planar and dual graphs. This paper also includes a brief discussion on non-planar Pythagorean fuzzy graphs and explores the concepts of isomorphism, weak isomorphism and co-weak isomorphism for Pythagorean fuzzy planar graphs. Moreover, it presents a problem that shows applicability of the proposed concept.

APA, Harvard, Vancouver, ISO, and other styles

42

Chattopadhyay, Arkadev, Jacobo Torán, and Fabian Wagner. "Graph Isomorphism is Not AC0-Reducible to Group Isomorphism." ACM Transactions on Computation Theory 5, no. 4 (November 2013): 1–13. http://dx.doi.org/10.1145/2540088.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Zhang, Miao, Ning Bo Liao, Chen Zhou, and Xi Tao. "Intelligent Design of Mechanism Kinematic Chains by Advanced Optimal Methods." Advanced Materials Research 201-203 (February 2011): 2182–85. http://dx.doi.org/10.4028/www.scientific.net/amr.201-203.2182.

Full text

Abstract:

When using graph theory to conduct intelligent design for kinematic structure enumeration, the isomorphism identification of graphs is an important and complicated problem. In this paper, the methodology of transferring isomorphism identification into optimization issue was introduced. Then the recent development of applying advanced optimal methods for isomorphism identification was reviewed, the advantages and disadvantages of there methods were discussed.

APA, Harvard, Vancouver, ISO, and other styles

44

Costalonga, João Paulo, Robert J. Kingan, and Sandra R. Kingan. "Constructing Minimally 3-Connected Graphs." Algorithms 14, no. 1 (January 1, 2021): 9. http://dx.doi.org/10.3390/a14010009.

Full text

Abstract:

A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. We present an algorithm for constructing minimally 3-connected graphs based on the results in (Dawes, JCTB 40, 159-168, 1986) using two operations: adding an edge between non-adjacent vertices and splitting a vertex. To test sets of vertices and edges for 3-compatibility, which depends on the cycles of the graph, we develop a method for obtaining the cycles of G′ from the cycles of G, where G′ is obtained from G by one of the two operations above. We eliminate isomorphic duplicates using certificates generated by McKay’s isomorphism checker nauty. The algorithm consecutively constructs the non-isomorphic minimally 3-connected graphs with n vertices and m edges from the non-isomorphic minimally 3-connected graphs with n−1 vertices and m−2 edges, n−1 vertices and m−3 edges, and n−2 vertices and m−3 edges.

APA, Harvard, Vancouver, ISO, and other styles

45

Morris, Christopher, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. "Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 4602–9. http://dx.doi.org/10.1609/aaai.v33i01.33014602.

Full text

Abstract:

In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion. Up to now, GNNs have only been evaluated empirically—showing promising results. The following work investigates GNNs from a theoretical point of view and relates them to the 1-dimensional Weisfeiler-Leman graph isomorphism heuristic (1-WL). We show that GNNs have the same expressiveness as the 1-WL in terms of distinguishing non-isomorphic (sub-)graphs. Hence, both algorithms also have the same shortcomings. Based on this, we propose a generalization of GNNs, so-called k-dimensional GNNs (k-GNNs), which can take higher-order graph structures at multiple scales into account. These higher-order structures play an essential role in the characterization of social networks and molecule graphs. Our experimental evaluation confirms our theoretical findings as well as confirms that higher-order information is useful in the task of graph classification and regression.

APA, Harvard, Vancouver, ISO, and other styles

46

Jenner, Birgit, Johannes Köbler, Pierre McKenzie, and Jacobo Torán. "Completeness results for graph isomorphism." Journal of Computer and System Sciences 66, no. 3 (May 2003): 549–66. http://dx.doi.org/10.1016/s0022-0000(03)00042-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Kwak, Jin Ho, and Jaeun Lee. "Isomorphism Classes of Graph Bundles." Canadian Journal of Mathematics 42, no. 4 (August 1, 1990): 747–61. http://dx.doi.org/10.4153/cjm-1990-039-3.

Full text

Abstract:

AbstractRecently, M. Hofmeister [4] counted all nonisomorphic double coverings of a graph by using its Ζ2 cohomology groups, and J. Kwak and J. Lee [5] did the same work for some finite-fold coverings. In this paper, we give an algebraic characterization of isomorphic graph bundles, from which we get a formula to count all nonisomorphic graph-bundles. Some applications to wheels are also discussed.

APA, Harvard, Vancouver, ISO, and other styles

48

Kijima, Shuji, Yota Otachi, Toshiki Saitoh, and Takeaki Uno. "Subgraph isomorphism in graph classes." Discrete Mathematics 312, no. 21 (November 2012): 3164–73. http://dx.doi.org/10.1016/j.disc.2012.07.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Arvind, V., and Piyush P. Kurur. "Graph Isomorphism is in SPP." Information and Computation 204, no. 5 (May 2006): 835–52. http://dx.doi.org/10.1016/j.ic.2006.02.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Klavík, Pavel, Dušan Knop, and Peter Zeman. "Graph isomorphism restricted by lists." Theoretical Computer Science 860 (March 2021): 51–71. http://dx.doi.org/10.1016/j.tcs.2021.01.027.

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!