Graph Isomorphism

LA home
  DF Trav
  Subg. Iso.
  Stable mrrg.

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.)


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

www #ad:

↑ © L. Allison,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Sunday, 16-Jun-2024 06:23:34 UTC.

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