Next:
GT34 MAXIMUM K-COLORABLE
Up:
Subgraphs and Supergraphs
Previous:
GT32 MAXIMUM EDGE
-
I
NSTANCE
:
Connected graph
.
-
S
OLUTION
:
A 2-spanner of
G
, i.e., a spanning subgraph
G'
of
G
such that, for
any pair
of vertices
u
and
v
, the shortest path between
u
and
v
in
G'
is at
most twice the shortest path between
u
and
v
in
G
.
-
M
EASURE
:
The number of edges in
G'
.
-
Good News:
Approximable within
[
241
].
-
Comment:
The variation in which the goal is to minimize the maximum degree in
G'
is
approximable within
where
is the
maximum degree in
G
[
243
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997