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

Mô tả đầy đủ

Chi tiết về thư mục
Xuất bản năm:Journal of the ACM 51, 3 (2004).
Tác giả chính: Alber, Jochen
Định dạng: Bài viết
Ngôn ngữ:English
Những chủ đề:
Theory of computation.
Analysis of algorithms and problem complexity.
Nonnumerical algorithms and problems.
Mathematics of computing.
Discrete mathematics.
Combinatorics.
Graph theory.
Algorithms.
Theory.