Next: Miscellaneous Up: Iso- and Other Morphisms Previous: MAXIMUM COMMON EMBEDDED SUB-TREE Index

### MINIMUM GRAPH TRANSFORMATION

- 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.