Loading...
Please wait, while we are loading the content...
Similar Documents
Polynomial-Time Data Reduction for DOMINATING SET (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Alber, Jochen Niedermeier, Rolf |
| 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 socalled 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. |
| File Format | |
| Journal | Journal of the ACM |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Subject Keyword | Problem Kernel Practical Side Polynomial-time Data Reduction Dominating Set Linear Size Combinatorial Optimization Important Problem Np-complete Dominating Set Problem Reduction Rule Graph Theory Impressive Practical Potential Data Reduction Prospective Way Undirected Graph First Experiment |
| Content Type | Text |
| Resource Type | Article |
