Publication: Optimization models for efficient (T, r) broadcast domination in graphs
3
Issued Date
2021-06-01
Resource Type
ISSN
20738994
Other identifier(s)
2-s2.0-85108704302
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Symmetry. Vol.13, No.6 (2021)
Suggested Citation
Poompol Buathong, Tipaluck Krityakierne Optimization models for efficient (T, r) broadcast domination in graphs. Symmetry. Vol.13, No.6 (2021). doi:10.3390/sym13061028 Retrieved from: https://repository.li.mahidol.ac.th/handle/123456789/76606
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Optimization models for efficient (T, r) broadcast domination in graphs
Author(s)
Other Contributor(s)
Abstract
Known to be NP-complete, domination number problems in graphs and networks arise in many real-life applications, ranging from the design of wireless sensor networks and biological networks to social networks. Initially introduced by Blessing et al., the (t, r) broadcast domination number is a generalization of the distance domination number. While some theoretical approaches have been addressed for small values of t, r in the literature; in this work, we propose an approach from an optimization point of view. First, the (t, r) broadcast domination number is formulated and solved using linear programming. The efficient broadcast, whose wasted signals are minimized, is then found by a genetic algorithm modified for a binary encoding. The developed method is illustrated with several grid graphs: regular, slant, and king’s grid graphs. The obtained computational results show that the method is able to find the exact (t, r) broadcast domination number, and locate an efficient broadcasting configuration for larger values of t, r than what can be provided from a theoretical basis. The proposed optimization approach thus helps overcome the limitations of existing theoretical approaches in graph theory.