Next:
GT23 MAXIMUM INDUCED
Up:
Subgraphs and Supergraphs
Previous:
GT21 MAXIMUM INDEPENDENT
GT22 M
AXIMUM
I
NDEPENDENT
S
EQUENCE
I
NSTANCE
: Graph
.
S
OLUTION
: An independent sequence for
G
, i.e., a sequence
of independent vertices of
G
such that, for all
i < m
, a vertex
exists which is adjacent to
but is not adjacent to any
for
.
M
EASURE
: Length of the sequence, i.e.,
m
.
Good News:
Approximable within
[
152
].
Bad News:
Not approximable within
for some
. [
56
].
Comment:
Transformation from M
AXIMUM
C
LIQUE
.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997