Next: Miscellaneous
Up: Iso- and Other Morphisms
Previous: MAXIMUM COMMON EMBEDDED SUB-TREE
  Index
- INSTANCE:
Graphs
and
.
- SOLUTION:
A transformation that makes
isomorphic to .
In the transformation
a set of edges
is removed from
and added to .
- MEASURE:
Cardinality of the transformation set, i.e., .
- Bad News:
APX-hard [359].
- Comment:
Transformation from MAXIMUM 3-SATISFIABILITY.
Viggo Kann
2000-03-20