- Title
- Polynomial-time data reduction for dominating set
- Creator
- Alber, Jochen; Fellows, Michael R.
- Relation
- Journal of the ACM Vol. 51, Issue 3, p. 363-384
- Publisher Link
- http://dx.doi.org/10.1145/990308.990309
- Publisher
- Association for Computing Machinery, Inc.
- Resource Type
- journal article
- Date
- 2004
- 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.
- Subject
- NP-complete problems; dominating set; plannar graphs; fixedparameter; problem kernel; data reduction
- Identifier
- http://hdl.handle.net/1959.13/31801
- Identifier
- uon:2818
- Identifier
- ISSN:1557-735x
- Language
- eng
- Full Text
- Reviewed
- Hits: 2202
- Visitors: 2337
- Downloads: 183
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Publisher version (open access) | 406 KB | Adobe Acrobat PDF | View Details Download |