Next: Miscellaneous
Up: Iso- and Other Morphisms
Previous: MAXIMUM COMMON EMBEDDED SUB-TREE
  Index
- INSTANCE:
Graphs
and
.
- SOLUTION:
A transformation that makes G1 isomorphic to G2. In the transformation
a set of edges
is removed from E1 and added to E2.
- MEASURE:
Cardinality of the transformation set, i.e., |E'|.
- Bad News:
APX-hard [340].
- Comment:
Transformation from MAXIMUM 3-SATISFIABILITY.
Viggo Kann
1999-04-22