Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/31801
- Title
- Polynomial-time data reduction for dominating set
- Author/Creator
-
Alber, Jochen;
Fellows, Michael R.
- Description
- 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.
- Relation
- Journal of the ACM Vol. 51, Issue 3, p. 363-384
- Publisher Link
- http://dx.doi.org/10.1145/990308.990309
- Date
- 2004
- Publisher
- Association for Computing Machinery, Inc.
- Keyword(s)
-
NP-complete problems;
dominating set;
plannar graphs;
fixedparameter;
problem kernel;
data reduction
- Resource Type
- journal article
- Identifier
- http://hdl.handle.net/1959.13/31801
- Identifier
- ISSN:1557-735x
- Reviewed
- Full Text
-
-
29 Visitors
34 Hits
2 Downloads
