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

Deskribapen osoa

Xehetasun bibliografikoak
Argitaratua izan da:Journal of the ACM 51, 3 (2004).
Egile nagusia: Alber, Jochen
Formatua: Artikulua
Hizkuntza:English
Gaiak:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Mathematics of computing.
Discrete mathematics.
Combinatorics.
Graph theory.
Algorithms.
Theory.