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

Ful tanımlama

Detaylı Bibliyografya

Yayımlandı:	Journal of the ACM 51, 3 (2004).
Yazar:	Alber, Jochen
Materyal Türü:	Makale
Dil:	English
Konular:	Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Mathematics of computing. Discrete mathematics. Combinatorics. Graph theory. Algorithms. Theory.