Graph Isomorphism

LA home
Computing
Algorithms
 glossary
 Graphs
  Directed
  DAG
  Undirected
  DF Trav
  Canonical
  Isomorphism
  Subg. Iso.
  Stable mrrg.
  Isomorphism

The graph isomorphism problem is to determine whether or not two graphs, G=<V,E> and G'=<V',E'>, are isomorphic. That is, does there exist a function f:V→V', that is 1-1 and onto, and such that <f(u),f(v)> is in E' (is an edge of G') exactly when <u,v> is in E.

The computational complexity of graph isomorphism is open in that it is clearly in NP but is not known to be in P or in NPC [as of 2010]. The more general subgraph isomorphism problem is known to be NP-complete (NPC).

One approach to graph isomorphism is to find canonical labellings, canon(G) of G, and canon(G') of G', G and G' being isomorphic iff canon(G)=canon(G'). (The computational complexity of the canonical labelling problem is therefore also open.)

Reading

Search for [isomorphism maths graph] in the computing bibliography.

www:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Wednesday, 11-Dec-2019 03:58:39 EST.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.