Next:
MINIMUM EDGE K-SPANNER
Up:
Subgraphs and Supergraphs
Previous:
MAXIMUM SUBFOREST
 
Index
M
AXIMUM
E
DGE
S
UBGRAPH
I
NSTANCE:
Graph
, a weight function
, and positive integer
k
.
S
OLUTION:
A subset
such that
.
M
EASURE:
Total weight of the edges in the subgraph induced by
V'
, i.e.,
Good News:
Approximable within
for some
[
157
].
Comment:
Also called
Dense
k
-subgraph
, or
Heavy subgraph
.
Approximable within 2 if the weights satisfy the triangle inequality [
241
]. The unweighted problem admits a PTAS if
and
[
39
].
Viggo Kann
2000-03-20