|Publisher version (open access)||406 KB||Adobe Acrobat PDF||View/Open
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/31801
- Polynomial-time data reduction for dominating set
Fellows, Michael R.
- 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 by two simple and easy-to-implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization.
- Journal of the ACM Vol. 51, Issue 3, p. 363-384
- Publisher Link
- Association for Computing Machinery, Inc.
- Resource Type
- journal article
- Full Text