×

zbMATH — the first resource for mathematics

Experiments on data reduction for optimal domination in networks. (English) Zbl 1106.90011
Summary: 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.

MSC:
90B10 Deterministic network models in operations research
Software:
BRITE; LEDA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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.
[2] 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. · Zbl 1016.68055 · doi:10.1007/s00453-001-0116-5
[3] 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. · Zbl 1101.68712
[4] Alber, J., M.R. Fellows, and R. Niedermeier. (2004).”Polynomial Time Data Reduction for Dominating Set.” Journal of the ACM, 51(3), 363–384. · Zbl 1192.68337 · doi:10.1145/990308.990309
[5] 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. · Zbl 05434783 · doi:10.1093/nar/29.1.242
[6] 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. · Zbl 1118.68506
[7] 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.
[8] Demaine, E.D. and M. Hajiaghayi. (2005).”Bidimensionality: New Connections Between FPT Algorithms and PTASs.” In Proc. 16th SODA, ACM/SIAM, pp. 590–601. · Zbl 1297.05056
[9] Feige, U. (1998).”A Threshold of ln n for Approximating Set Cover.” Journal of the ACM, 45(4):634–652. · Zbl 1065.68573 · doi:10.1145/285055.285059
[10] 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. · Zbl 1094.68610
[11] Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. · Zbl 0411.68039
[12] 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. · Zbl 1122.68481
[13] 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. · Zbl 1006.05043 · doi:10.1137/S0895480100375831
[14] 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. · Zbl 0883.00011
[15] 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. · Zbl 0890.05002
[16] Jin, C., Q. Chen, and S. Jamin. (2001).”Inet: Internet Topology Generator.” Technical Report CSE-TR443-00, Department of EECS, University of Michigan.
[17] Kratsch, D. (1998).”Algorithms.” In T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, (eds.), Domination in Graphs: Advanced Topics. Marcel Dekker. · Zbl 0883.00011
[18] Medina, A., A. Lakhina, I. Matta, and J.W. Byers. (2001).”Brite: An Approach to Universal Topology Generation.” In Proc. MASCOTS.
[19] Mehlhorn, K. and S. Näher. (1999). LEDA: A Platform of Combinatorial and Geometric Computing. Cambridge University Press. · Zbl 0976.68156
[20] Roberts, F.S. (1979). Graph Theory and Its Applications to Problems of Society. SIAM Press, Odyssey Press.
[21] Sanchis, L.A. (2002).”Experimental Analysis of Heuristic Algorithms for the Dominating Set problem.” Algorithmica, 33(1), 3–18. · Zbl 0994.68092 · doi:10.1007/s00453-001-0101-z
[22] 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. · doi:10.2105/AJPH.93.11.1837
[23] 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. · Zbl 1075.68066 · doi:10.1142/S0129054103001753
[24] Weihe, K. (1998).”Covering Trains by Stations or the Power of Data Reduction.” In Proc. 1st ALEX’98, pp. 1–8.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.