Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58
Richard Schroeppel (rcs@cs.arizona.edu)
Fri, 14 Aug 1998 07:23:18 MST
The NP-complete problem is SUBgraph isomorphism:
Given two graphs G and H, is there an isomorphism of G to
some subgraph of H? (This is only interesting when H is
at least as big as G.)
The Graph Isomorphism problem is to decide if two graphs G
and H are isomorphic. (This is only interesting when the
graphs are the same size.) This problem is a candidate for
being in between NP and P, but nothing is proved.
Two graphs G and H are isomorphic when there's a matchup between
vertices in G and H, and the predicate Edge?(v1,v2) is preserved
by the matchup.
In the subgraph isomorphism problem, the subgraphs of H are built
by deleting (0 or more) vertices, deleting the edges connecting
to those vertices, and deleting (0 or more) additional edges.
No path-coalescing is used. (Some graph problems allow coalescing,
in which two edge-connected vertices are merged.)
Sometimes people say "Graph Isomorphism" when they mean "Subgraph
Isomorphism". This can be very confusing to the audience.
Rich Schroeppel rcs@cs.arizona.edu
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58