MINIMUM EDGE DOMINATING SET

Next: MINIMUM INDEPENDENT DOMINATING SET Up: Covering and Partitioning Previous: MAXIMUM DOMATIC PARTITION Index

INSTANCE: Graph $G=\left(V,E\right)$ .
SOLUTION: An edge dominating set for G, i.e., a subset $E'\subseteq E$ such that for all $e_1\in E-E'$ there is an $e_2\in E'$ such that and are adjacent.
MEASURE: Cardinality of the edge dominating set, i.e., $\vert E'\vert$ .
Good News: Approximable within 2 (any maximal matching).
Comment: Admits a PTAS for planar graphs [53] and for $\lambda$ -precision unit disk graphs [264].
Garey and Johnson: GT2

Viggo Kann
2000-03-20