Next:
Miscellaneous
Up:
Iso- and Other Morphisms
Previous:
GT44 MAXIMUM COMMON
GT45 M
INIMUM
G
RAPH
T
RANSFORMATION
I
NSTANCE
: Graphs
and
.
S
OLUTION
: A transformation that makes
isomorphic to
. In the transformation a set of edges
is removed from
and added to
.
M
EASURE
: Cardinality of the transformation set, i.e.,
|E'|
.
Bad News:
A
PX
-hard [
258
].
Comment:
Transformation from M
AXIMUM
3-S
ATISFIABILITY
.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
and
.
isomorphic to
. In the transformation
a set of edges
is removed from
and added to
.