Polynomial-time data reduction for dominating set

DOI10.1145/990308.990309zbMATH Open1192.68337DBLPjournals/jacm/AlberFN04arXivcs/0207066OpenAlexW2093762675WikidataQ57360014 ScholiaQ57360014MaRDI QIDQ3583575

Author name not available (Why is that?)

Publication date: 17 August 2010

Published in: (Search for Journal in Brave)

Abstract: Dealing with the NP-complete Dominating Set problem on undirected 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.

Full work available at URL: https://arxiv.org/abs/cs/0207066

Mathematics Subject Classification ID

No records found.

This page was built for publication: Polynomial-time data reduction for dominating set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3583575)