Next: MINIMUM INDEPENDENT DOMINATING SET
Up: Covering and Partitioning
Previous: MINIMUM DOMINATING SET
  Index
- INSTANCE:
Graph
.
- SOLUTION:
An edge dominating set for G, i.e., a subset
such that for
all
there is an
such that e1 and e2 are
adjacent.
- MEASURE:
Cardinality of the edge dominating set, i.e., |E'|.
- Good News:
Approximable within 2 (any maximal matching).
- Comment:
Admits a PTAS for planar graphs [50]
and for
-precision unit disk graphs [249].
- Garey and Johnson: GT2
Viggo Kann
1999-04-22