Next:
MAXIMUM EDGE SUBGRAPH
Up:
Subgraphs and Supergraphs
Previous:
MAXIMUM K-COLORABLE SUBGRAPH
Index
M
AXIMUM
S
UBFOREST
I
NSTANCE:
Tree
and a set of trees
H
.
S
OLUTION:
A subset
such that the subgraph
does not contain any subtree isomorphic to a tree from
H
.
M
EASURE:
Cardinality of the subgraph, i.e.,
.
Good News:
Admits a PTAS [
438
].
Viggo Kann
2000-03-20