Polynomial Time Data Reduction for Dominating Set

Details Polynomial Time Data Reduction for Dominating Set Polynomial Time Data Reduction for Dominating Set

2002-07-16

arxiv.org/abs/cs/0207066v1

Computer Science

Data Structures and Algorithms

25 pages, 4 figures (using 8 files), extended abstract entitled "Efficient Data Reduction for Dominating Set: A Linear Problem

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Polynomial Time Data Reduction for Dominating Set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial Time Data Reduction for Dominating Set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Time Data Reduction for Dominating Set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-42845