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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alber, J. (2003). Exact Algorithms for NP-hard Problems on Networks: Design, Analysis, and Implementation. PhD thesis, WSI für Informatik, Universität Tübingen, Germany.
Alber, J., H.L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. (2002).“Fixed Parameter Algorithms for Dominating Set and Related Problems on Planar Graphs.” Algorithmica, 33(4), 461–493.
Alber, J., H. Fan, M.R. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, and U. Stege. (2005).“ A Refined Search Tree Technique for Dominating Set on Planar Graphs. ” Journal of Computer and System Sciences 71(4), 385–405.
Alber, J., M.R. Fellows, and R. Niedermeier. (2004).“Polynomial Time Data Reduction for Dominating Set.” Journal of the ACM, 51(3), 363–384.
Bader, G.D., I. Donaldson, C. Wolting, B.F.F. Quellette, T. Pawson, and C.W.V. Hogue. (2001).“BIND—The Biomolecular Interaction Network Database.” Nucleic Acids Research, 29(1), 242–245.
Chen, J., H. Fernau, I.A. Kanj, and G. Xia. (2005). “Parametric Duality and Kernelization: Lower Bounds and upper Bounds on Kernel Size.” In Proc. 22d STACS, vol. 3404 of LNCS, Springer, pp. 269–280.
Chen, Q., H. Chang, R. Govindan, S. Jamin, S. Shenker, and W. Willinger. (2002).“The Origin of Power-Laws in Internet Topologies Revisited.” In Proc. of INFOCOM.
Demaine, E.D. and M. Hajiaghayi. (2005).“Bidimensionality: New Connections Between FPT Algorithms and PTASs.” In Proc. 16th SODA, ACM/SIAM, pp. 590–601.
Feige, U. (1998).“A Threshold of ln n for Approximating Set Cover.” Journal of the ACM, 45(4):634–652.
Fomin, F.V. and D.M Thilikos. (2003).“Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up.” In Proc. 14th SODA, ACM/SIAM, pp. 168–177.
Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.
Guo, J., R. Niedermeier, and D. Raible. (2005).“Improved Algorithms and Complexity Results for Power Domination in Graphs.” In Proc. 15th FCT, volume 3623 of LNCS. Springer pp. 172–184.
Haynes, T.W., S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning. (2002).“Domination in Graphs Applied to Electric Power Networks.” SIAM Journal on Discrete Mathematics, 15(4), 519–529.
Haynes, T.W., S.T. Hedetniemi, and P.J. Slater. (1998a). Domination in Graphs: Advanced Topics, vol. 209 of Pure and Applied Mathematics. Marcel Dekker.
Haynes, T.W., S.T. Hedetniemi, and P.J. Slater. (1998b). Fundamentals of Domination in Graphs, vol. 208 of Pure and Applied Mathematics. Marcel Dekker.
Jin, C., Q. Chen, and S. Jamin. (2001).“Inet: Internet Topology Generator.” Technical Report CSE-TR443-00, Department of EECS, University of Michigan.
Kratsch, D. (1998).“Algorithms.” In T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, (eds.), Domination in Graphs: Advanced Topics. Marcel Dekker.
Medina, A., A. Lakhina, I. Matta, and J.W. Byers. (2001).“Brite: An Approach to Universal Topology Generation.” In Proc. MASCOTS.
Mehlhorn, K. and S. Näher. (1999). LEDA: A Platform of Combinatorial and Geometric Computing. Cambridge University Press.
Roberts, F.S. (1979). Graph Theory and Its Applications to Problems of Society. SIAM Press, Odyssey Press.
Sanchis, L.A. (2002).“Experimental Analysis of Heuristic Algorithms for the Dominating Set problem.” Algorithmica, 33(1), 3–18.
Valente, T.W., B.R. Hoffman, A. Ritt-Olson, K. Lichtman, and C.A. Johnson. (2003).“Strategies on Peer-Led Tobacco Prevention Programs in Schools.” American Journal of Public Health, 93(11), 1837–1843.
Wan, P.-J., K.M. Alzoubi, and O. Frieder. (2003).“A Simple Heuristic for Minimum Connected Dominating Set in Graphs.” International Journal of Foundations of Computer Science, 14(2), 323–333.
Weihe, K. (1998).“Covering Trains by Stations or the Power of Data Reduction.” In Proc. 1st ALEX'98, pp. 1–8.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the Deutsche Forschungsgemeinschaft (DFG), project PEAL (parameterized complexity and exact algorithms), NI 369/1 and junior research group PIAF (fixed-parameter algorithms), NI 369/4. Main work done while all authors were with Universität Tübingen. An extended abstract of this paper appeared in the Proceedings of the International Network Optimization Conference (INOC 2003), pages 1–6, held in Evry/Paris, France, October 27–29, 2003.
Rights and permissions
About this article
Cite this article
Alber, J., Betzler, N. & Niedermeier, R. Experiments on data reduction for optimal domination in networks. Ann Oper Res 146, 105–117 (2006). https://doi.org/10.1007/s10479-006-0045-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-006-0045-4