Polynomial-time data reduction for dominating set.
Dealing with the NP-complete Dominating Set problem on graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a so-called problem kernel of linear size, achieved b...
| Εκδόθηκε σε: | Journal of the ACM 51, 3 (2004). |
|---|---|
| Κύριος συγγραφέας: | |
| Μορφή: | Άρθρο |
| Γλώσσα: | Αγγλικά |
| Θέματα: |