|
|||||
|
|
Experiments on data reduction for optimal domination in networks |
|
| Authors: | Jochen Alber Nadja Betzler Rolf Niedermeier |
| Affiliation: | 1. Power System Applications ? Consulting, DIgSILENT GmbH, Heinrich-Hertz-Str.9, D-72810, Gomaringen, Germany 2. Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen, Sand 13, D-72076, Tübingen, Germany 3. Institut für Informatik, Friedrich-Schiller-Universit?t Jena, Ernst-Abbe-Platz 2, D-07743, Jena, Germany |
| Abstract: | We present empirical results on computing optimal dominating sets in networks by means of data reduction through efficient preprocessing rules. Thus, we demonstrate the usefulness of so far only theoretically considered data reduction techniques for practically solving one of the most important network problems in combinatorial optimization. |
| Keywords: | Experimental study Domination NP-complete problem Preprocessing by data reduction rules Optimal solutions Network optimization |
| 本文献已被 SpringerLink 等数据库收录！ | |