Articles
| Open Access |
OPTIMIZING STEINER TREES: MINIMIZING STEINER POINTS FOR EFFICIENT NETWORK CONNECTIVITY
Nachshon Nutov , Federal Polytechnic School of Lausanne (EPFL), SwitzerlandAbstract
This research focuses on the optimization of Steiner trees by minimizing the number of Steiner points, aiming for efficient network connectivity. Steiner trees play a crucial role in designing cost-effective networks by connecting specified terminal nodes with additional Steiner points. Our study explores algorithms and approaches to approximate Steiner trees and forests while minimizing the required Steiner points. The goal is to enhance network efficiency, reduce resource utilization, and facilitate the design of streamlined communication networks. This abstract provides an overview of the methodology, key findings, and implications of the research in the realm of network optimization.
Keywords
Steiner trees, network connectivity, Steiner points
References
Agrawal, P. Klein, R. Ravi, When trees collide: an approximation algorithm for the generalized steiner problem on networks, SIAM J. Comput. 24 (3) (1995) 440–456.
J. Bredin, E. Demaine, M. Hajiaghayi, D. Rus, Deploying sensor networks with guaranteed fault tolerance, IEEE/ACM Trans. Netw. 18 (1) (2010) 216–228.
J. Byrka, F. Grandoni, T. Rothvoß, L. Sanità, Steiner tree approximation via iterative randomized rounding, J. ACM 60 (1) (2013).
G. Calinescu, Relay placement for two-connectivity, in: Networking, vol. 2, 2012, pp. 366–377.
G. Calinescu, B. Grimmer, S. Misra, S. Tongngam, G. Xue, W. Zhang, Improved approximation algorithms for single-tiered relay placement, J. Comb.
D. Chen, D.-Z. Du, X.-D. Hu, G.-H. Lin, L. Wang, G. Xue, Approximations for Steiner trees with minimum number of steiner points, Theor. Comput. Sci. 262 (1) (2001) 83–99.
X. Cheng, D. Du, L. Wang, B. Xu, Relay sensor placement in wireless sensor networks, Wirel. Netw. 14 (3) (2008) 347–355.
N. Cohen, Z. Nutov, A (1 + ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius, Theor. Comput. Sci. 67–74 (2013) 489–490.
D.-Z. Du, Y. Zhang, On better heuristics for Steiner minimum trees, Math. Program. 57 (1992) 193–202.
L. Fleischer, K. Jain, D.P. Williamson, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, J. Comput. Syst. Sci. 72 (5) (2006) 838–867.
Article Statistics
Downloads
Copyright License
Copyright (c) 2024 Nachshon Nutov
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright and Ethics:
- Authors are responsible for obtaining permission to use any copyrighted materials included in their manuscript.
- Authors are also responsible for ensuring that their research was conducted in an ethical manner and in compliance with institutional and national guidelines for the care and use of animals or human subjects.
- By submitting a manuscript to International Journal of Computer Science & Information System (IJCSIS), authors agree to transfer copyright to the journal if the manuscript is accepted for publication.