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.
References in periodicals archive ?
Other subjects covered include planar graph isomorphism in log-space, quantum copy-protection and quantum money, reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in, worst-case running times for average-case algorithms, and new results in the simultaneous message passing model via information theoretic techniques.
As an immediate consequence of the Church-Rosser property, the graph r(G) above is unique up to graph isomorphism.
the graph isomorphism is "interchange the ith and (i + 1)th vertices.