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

Cur síos iomlán

Sonraí bibleagrafaíochta
Foilsithe in:Journal of the ACM 51, 3 (2004).
Príomhchruthaitheoir: Alber, Jochen
Formáid: Alt
Teanga:English
Ábhair:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Mathematics of computing.
Discrete mathematics.
Combinatorics.
Graph theory.
Algorithms.
Theory.