2004/05/01 by Jochen Alber, Michael R. Fellows, Rolf Niedermeier · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Dominating set #Reduction (mathematics) #Preprocessor #Computer science #Time complexity #Set (abstract data type) #Mathematics #Graph #Independent set #Simple (philosophy) #Algorithm #Theoretical computer science #Artificial intelligence
paper · doi:10.1145/990308.990309
openalex publication_date 2004/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/21
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 by two simple and easy-to-implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization.