Polynomial-time data reduction for dominating set.

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...

Volledige beschrijving

Bibliografische gegevens
Gepubliceerd in:Journal of the ACM 51, 3 (2004).
Hoofdauteur: Alber, Jochen
Formaat: Artikel
Taal:English
Onderwerpen:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Mathematics of computing.
Discrete mathematics.
Combinatorics.
Graph theory.
Algorithms.
Theory.