Graph 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 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
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.) ReadingSearch for |
|
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso-8859-1, fetched Thursday, 15-Apr-2021 10:26:08 EDT. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off. |