isomorphism problem

(redirected from Graph isomorphism)
Also found in: Wikipedia.

isomorphism problem

[‚ī·sə′mȯr‚fiz·əm ‚präb·ləm]
(mathematics)
For two simple graphs with the same numbers of vertices and edges, the problem of determining whether there exist correspondences between these vertices and edges such that there is an edge between two vertices in one graph if and only if there is an edge between the corresponding vertices in the other.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
References in periodicals archive ?
The most stringent pattern of exact-matching algorithms is graph isomorphism, which requires the mapping of nodes and edges on both graphs to bebijections [21].
Thus, [empty set] is a Neutrosophic graph isomorphism from Ne(G, I) onto Ne(G', I'), that is, Ne(G, I) [congruent to] Ne(G', I').
The first one provides the results of graph isomorphism. The second describes the relation between edge conditions of the Farey graph F and the Farey sequences.
Meanwhile, in [25] an algorithm for graph isomorphism at large scale is shown.
In the structural synthesis process of gear train kinematic chains, correctly identifying graph isomorphism is an important step which generates new structural types.
(This is expected, as computing graph isomorphism remains a computationally challenging problem.
A new algorithm efficiently solves the graph isomorphism problem, computer scientist Laszlo Babai announced November 10 at a Combinatorics and Theoretical Computer Science seminar at the University of Chicago.
By computer search, we find that there is one modular Leech tree for n = 8 and the edge-weighting function is unique, up to group and graph isomorphism. It is shown in Figure 3.
Graph automorphism (GA), graph isomorphism (GI), and finding of a canonical labeling (CL) are closely related classical graph problems that have applications in many fields, ranging from mathematical chemistry [1, 2] to computer vision [3].
* Martin Fiirer (Penn State U.): Combinatorial Methods for the Graph Isomorphism Problem
This example is a particular instance of the graph isomorphism problem, for which there is no polynomial time algorithm yet, while our algorithm seems to solve the problem.