1.5.9 Graph Isomorphism
INPUT OUTPUT
Input Description:
Two graphs,
g
and
h
.}
Problem:
Find a (all) mappings
f
of the vertices of
g
to the vertices
of
h
such that
g
and
h
are identical, ie.
(x,y)
is an
edge of
g
iff
(f(x),f(y))
is an edge of
h
.
Implementations
NAUTY -- Graph Isomorphism (C) (rating 10)
Combinatorica (Mathematica) (rating 3)
Related Problems
Generating Graphs
Shape Similarity
Shortest Path
String Matching
Go to the corresponding chapter in the book
About the Book
Send us Mail
Go to Main Page
This page last modified on Tue Jun 03, 1997
.