Ir al contenido

Documat

A survey on dominating sets: bounds and algorithms

  • Ernesto Parra-Inza [1] ; José M. Sigarreta-Almira [2] Árbol académico ; Nodari Vakhania [1] ; Juan C. Hernández-Gómez [2]
    1. [1] Universidad Autónoma del Estado de Morelos

      Universidad Autónoma del Estado de Morelos

      México

    2. [2] Universidad Autónoma de Guerrero

      Universidad Autónoma de Guerrero

      México

  • Localización: BEIO, Boletín de Estadística e Investigación Operativa, ISSN 1889-3805, Vol. 41, Nº. 1, 2025, págs. 32-50
  • Idioma: inglés
  • Enlaces
  • Resumen

    • A subset S of vertices in a graph G is called a dominating set of G if every vertex in G has at least one neighbor in S or is in S. In this article, we provide an accessible introduction to the fundamental concepts of domination in graphs, exploring its importance and applications in areas such as networks, biology, and optimization through examples and recent results.

  • Referencias bibliográficas
    • Alon, N. y Gutner, S. (2009). Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica, 54, 544–556....
    • Balasundaram, B. y Butenko, S. (2006). Graph domination, coloring and cliques in telecommunications. In Handbook of optimization in telecommunications...
    • Ball, W. W. R. (1914). Mathematical recreations and essays. Fourth Edition, Macmillan.
    • Berge, C. (1958). The theory of graphs and its applications. Methuen, London.
    • Bouamama, S. y Blum, C. (2021). An improved greedy heuristic for the minimum positive influence dominating set problem in social networks....
    • Brigham, R. C. y Dutton, R. D. (1990). Factor domination in graphs. Discrete Mathematics, 86(1), 127-136. doi: https://doi.org/ 10.1016/0012-365X(90)90355-L
    • Bulo, S. R. y Pelillo, M. (2017). Dominant-set clustering: A review. ` European Journal of Operational Research, 262(1), 1–13. doi: https://doi.org/10.1016/j.ejor.2017.03.056
    • Cabrera Mart´ınez, A., Hernandez-G ´ omez, J. C., Inza, E. P. y Sigarreta, J. M. (2020). On the total outer k-independent domination ´ number...
    • Campan, A., Truta, T. M. y Beckerich, M. (2015). Fast dominating set algorithms for social networks. In Maics (pp. 55–62).
    • Casado, A., Bermudo, S., Lopez-S ´ anchez, A. y S ´ anchez-Oro, J. (2023). An iterated greedy algorithm for finding the minimum ´ dominating...
    • Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D. y Trevisan, L. (2020). From gap-exponential time...
    • Chalupa, D. (2018). An order-based algorithm for minimum dominating set with application in graph mining. Information Sciences, 426, 101–116....
    • Chellali, M., Favaron, O., Hansberg, A. y Volkmann, L. (2012). k-domination and k-independence in graphs: A survey. Graphs and Combinatorics,...
    • Chlebík, M. y Chleb´ıkova, J. (2004). Approximation hardness of dominating set problems. In ´ Algorithms–esa 2004: 12th annual european symposium,...
    • Chvatal, V. (1979). A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3), 233–235. doi: https://doi.org/10.1287/moor.4.3.233
    • Cockayne, E., Goodman, S. y Hedetniemi, S. (1975). A linear algorithm for the domination number of a tree. Information Processing Letters,...
    • Davidson, P. P., Blum, C. y Lozano, J. A. (2018). The weighted independent domination problem: Integer linear programming models and metaheuristic...
    • Dinh, T. N., Shen, Y., Nguyen, D. T. y Thai, M. T. (2014). On the approximability of positive influence dominating set in social networks....
    • Du, D.-Z. y Wan, P.-J. (2012). Connected dominating set: theory and applications (Vol. 77). Springer Science & Business Media. doi: https://doi.org/10.1007/978-1-4614-5242-3
    • Dudeney, H. E. (1908). The canterbury puzzles and other curious problems. E. P. Dutton and Company, New York.
    • Erlebach, T. y Van Leeuwen, E. J. (2008). Domination in geometric intersection graphs. In Latin american symposium on theoretical informatics...
    • Eubank, S., Kumar, V. A., Marathe, M. V., Srinivasan, A. y Wang, N. (2004). Structural and algorithmic aspects of massive social networks....
    • Fan, N. y Watson, J.-P. (2012). Solving the connected dominating set problem and power dominating set problem by integer programming. In International...
    • Feldmann, A. E., Karthik, C., Lee, E. y Manurangsi, P. (2020). A survey on approximation in parameterized complexity: Hardness and algorithms....
    • Flach, P. y Volkmann, L. (1990). Estimations for the domination number of a graph. Discrete mathematics, 80(2), 145–151.
    • Foerster, K.-T. (2013). Approximating fault-tolerant domination in general graphs. In 2013 proceedings of the tenth workshop on analytic algorithmics...
    • Fomin, F. V., Grandoni, F. y Kratsch, D. (2009). A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM...
    • Fomin, F. V., Kratsch, D. y Woeginger, G. J. (2004). Exact (exponential) algorithms for the dominating set problem. In Graph-theoretic concepts...
    • Fotouhi, F., Balu, A., Jiang, Z., Esfandiari, Y., Jahani, S. y Sarkar, S. (2024). Dominating set model aggregation for communication-efficient...
    • Garey, M. R. y Johnson, D. S. (1979). Computers and intractability (Vol. 174). freeman San Francisco.
    • Gaspers, S., Kratsch, D., Liedloff, M. y Todinca, I. (2009). Exponential time algorithms for the minimum dominating set problem on some graph...
    • Gibson, M. y Pirwani, I. A. (2010). Approximation algorithms for dominating set in disk graphs. arXiv preprint arXiv:1004.3320. doi: https://doi.org/10.48550/arXiv.1004.3320
    • Guha, S. y Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20, 374–387. doi: https://doi.org/10.1007/PL00009201
    • Haynes, T. (2017). Domination in graphs: Volume 2: Advanced topics. Routledge.
    • Haynes, T. W., Hedetniemi, S. y Slater, P. (1998). Fundamentals of domination in graphs. Marcel Dekker, Inc., New York.
    • Haynes, T. W., Hedetniemi, S. M., Hedetniemi, S. T. y Henning, M. A. (2002). Domination in graphs applied to electric power networks. SIAM...
    • Haynes, T. W., Hedetniemi, S. T. y Henning, M. A. (2020). Topics in domination in graphs (Vol. 64). Springer. doi: https://doi.org/ 10.1007/978-3-030-51117-3
    • Henning, M. A. (2009). A survey of selected recent results on total domination in graphs. Discrete Mathematics, 309(1), 32–63. doi: https://doi.org/10.1016/j.disc.2007.12.044
    • Henning, M. A. y Yeo, A. (2013). Total domination in graphs. Springer. doi: https://doi.org/10.1007/978-1-4614-6525-6
    • Hunt III, H. B., Marathe, M. V., Radhakrishnan, V., Ravi, S. S., Rosenkrantz, D. J. y Stearns, R. E. (1998). Nc-approximation schemes for...
    • Inza, E. P., Vakhania, N., Almira, J. M. S. y Mira, F. A. H. (2024). Exact and heuristic algorithms for the domination problem. European Journal...
    • Iwata, Y. (2012). A faster algorithm for dominating set analyzed by the potential method. In International symposium on parameterized and...
    • Joshi, D. S., Radhakrishnan, S. y Chandrasekharan, N. (1994). The k-neighbor, r-domination problems on interval graphs. European Journal of...
    • Kikuno, T., Yoshida, N. y Kakuda, Y. (1983). A linear algorithm for the domination number of a series-parallel graph. Discrete Applied Mathematics,...
    • Konig, D. (1950). ¨ Theorie der endlichen und unendlichen graphen. Akademische Verlagsgesellschaft M. B. H., Leipzig, 1936, later Chelsea,...
    • Li, Y., Thai, M. T., Wang, F., Yi, C.-W., Wan, P.-J. y Du, D.-Z. (2005). On greedy construction of connected dominating sets in wireless networks....
    • Liao, C.-S. y Lee, D.-T. (2005). Power domination problem in graphs. In International computing and combinatorics conference (pp. 818–828)....
    • Lick, D. R. y White, A. T. (1970). k-degenerate graphs. Canadian Journal of Mathematics, 22(5), 1082–1096. doi: https://doi.org/ 10.4153/CJM-1970-125-1
    • Lin, B. (2019). A simple gap-producing reduction for the parameterized set cover problem. arXiv preprint arXiv:1902.03702.
    • Liu, C.-H., Poon, S.-H. y Lin, J.-Y. (2015). Independent dominating set problem revisited. Theoretical Computer Science, 562, 1–22. doi: https://doi.org/10.1016/j.tcs.2014.09.001
    • Mira, F. A. H., Inza, E. P., Sigarreta, J. M. y Vakhania, N. (2022). A polynomial-time approximation to a minimum dominating set in a graph....
    • Nieberg, T., Hurink, J. y Kern, W. (2008). Approximation schemes for wireless networks. ACM Transactions on Algorithms (TALG), 4(4), 1–17....
    • Ore, O. (1962). Theory of graphs. In Colloquium publications (Vol. 38).
    • Pan, J.-S., Kong, L., Sung, T.-W., Tsai, P.-W. y Sna´sel, V. (2018). A clustering scheme for wireless sensor networks based on genetic ˇ algorithm...
    • Parekh, A. K. (1991). Analysis of a greedy heuristic for finding small dominating sets in graphs. Information processing letters, 39(5), 237–240....
    • Parra Inza, E. (2023). Random graph (1). Mendeley Data, V4. doi: https://doi.org/10.17632/rr5bkj6dw5.4
    • Parra Inza, E., Sandoval Ram´ırez, A., Hernandez G ´ omez, J. y Cerdenares Ladr ´ on de Guevara, G. (2021). ´ Analisis de la robustez de ´ redes...
    • Parra Inza, E., Vakhania, N., Sigarreta Almira, J. M. y Hernandez-Aguilar, J. A. (2024). Approximating a minimum dominating set by ´ purification....
    • Potluri, A. y Singh, A. (2011). Two hybrid meta-heuristic approaches for minimum dominating set problem. In Swarm, evolutionary, and memetic...
    • Potluri, A. y Singh, A. (2013). Hybrid metaheuristic algorithms for minimum weight dominating set. Applied Soft Computing, 13(1), 76–88. doi:...
    • Priyadarshini, R. R. y Sivakumar, N. (2021). Cluster head selection based on minimum connected dominating set and bi-partite inspired methodology...
    • Raz, R. y Safra, S. (1997). A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of...
    • Reed, B. (1996). Paths, stars and the number three. Combinatorics, Probability and Computing, 5(3), 277–295. doi: https://doi.org/ 10.1017/S0963548300002042
    • Sampathkumar, E. y Walikar, H. (1979). The connected domination number of a graph. J. Math. Phys, 13(6).
    • Schiermeyer, I. (2008). Efficiency in exponential time for domination-type problems. Discrete Applied Mathematics, 156(17), 3291-3297. (Cologne/Twente...
    • Schoenmakers, L. A. M. (1995). A new algorithm for the recognition of series parallel graphs. Centrum voor Wiskunde en Informatica Amsterdam.
    • Siebertz, S. (2019). Greedy domination on biclique-free graphs. Information Processing Letters, 145, 64–67. doi: https://doi.org/ 10.1016/j.ipl.2019.01.006
    • Thai, M. T., Wang, F., Liu, D., Zhu, S. y Du, D.-Z. (2007). Connected dominating sets in wireless networks with different transmission ranges....
    • Van Rooij, J. M. y Bodlaender, H. L. (2011). Exact algorithms for dominating set. Discrete Applied Mathematics, 159(17), 2147–2164. doi: https://doi.org/10.1016/j.dam.2011.07.001
    • Venkataraman, Y., Kalaiselvi, T., Angelina, J. J. R. y Janakiram, S. S. (2023). Dominating sets in protein-protein interaction networks. In...
    • Wan, P.-J., Alzoubi, K. M. y Frieder, O. (2004). Distributed construction of connected dominating set in wireless ad hoc networks. Mobile...
    • Wang, F., Du, H., Camacho, E., Xu, K., Lee, W., Shi, Y. y Shan, S. (2011). On positive influence dominating sets in social networks. Theoretical...
    • Wang, Q., Nute, M. y Treangen, T. J. (2023). Bakdrive: identifying a minimum set of bacterial species driving interactions across multiple...
    • Wang, Y., Cai, S., Chen, J. y Yin, M. (2018). A fast local search algorithm for minimum weight dominating set problem on massive graphs. In...
    • Wu, J. (2002). Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE transactions on parallel...
    • Wu, J., Wu, B. y Stojmenovic, I. (2003). Power-aware broadcasting and activity scheduling in ad hoc wireless networks using connected dominating...
    • Yu, J., Wang, N., Wang, G. y Yu, D. (2013). Connected dominating sets in wireless ad hoc and sensor networks–a comprehensive survey. Computer...
    • Alvarez Miranda, E. y Sinnl, M. (2021). Exact and heuristic algorithms for the weighted total domination problem. ´ Computers & Operations...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno