
[27], this tool is already able to successfully solve
exponentially complex problems with data struc-
tures with thousands of rows and columns. Here,
we verified that it is able to find exact solutions
for graphs with up to 100 vertices.
However, more tests will need to be performed
in the future to compare the results with bench-
mark data from combinatorial optimization li-
braries as [4], [23].
,
,
,
,
,
References:
[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network
Flows. Theory, Algorithms and Applications. Prentice Hall,
Englewood Cliffs, New Jersey, 1993. ISBN 0-13-617549- X.
[2] S. Balaji, K. Kannan, and Y. B. Venkatakrishnan. Total
Dominating Set Based Algorithm for Connected Dominating
Set in Ad hoc Wireless Networks. WSEAS Transactions on
Mathematics, 12:1164–1172, 2013.
[3] V. K. Balakrishnan. Network Optimization. Chapman &
Hall Mathematics, London, 1995.
[4] J. E. Beasley. OR-Library. Report, The Management School
Imperial College, London, 1996.
http://mscmga.ms.ic.ac.uk/info.html.
[5] C. Bentz, M.-C. Costa, and A. Herty. On the Edge
Capacitated Steiner Tree Problem. Discrete Optimization,
38:1–25, 2020.
[6] A. Brooke, D. Kendrick, and A. Meeraus. GAMS Release
2.25. A User’s Guide. The Scientific Press. Boyd & Fraser
Publishing Company, Massachussets, 1992.
[7] J.-F. Camacho-Vallejo and C. Garcia-Reyes. Co-
Evolutionary Algorithms to Solve Hierarchized Steiner Tree
Problems in Telecommunication Nnetworks. Applied Soft
Computing Journal, 84:1–12, 2019.
[8] C.-Y. Chen and S.-Y. Hsieh. An Improved Algorithm for
the Steiner Tree Problem with Bounded Edge-Length. Journal
of Computer and System Sciences, 123:20–36, 2022.
[9] D. Du and X. Hu. Steiner Tree Problems in Computer
Communication Networks. World Scientific, Singapore, 2008.
[10] D.-Z. Du, J. M. Smith, and J. H. Rubinstein. Advances in
Steiner Trees. Kluwer Academic Publishers, Dordrecht, 2000.
ISBN 0-7923- 6110-5.
[11] C. W. Duin and A. Volgenant. The Partial Sum Criterion
for Steiner Trees in Graphs and Shortest Paths. European
Journal of Operational Research, 97:172–182, 1997.
[12] D. Gaul and D. R. Schmidt. Chv´atal–Gomory Cuts for the
Steiner Tree Problem. Discrete Applied Mathematics,
291:188–200, 2021.
[13] M.X. Goemans and Y. Myung. A Catalog of Steiner Tree
Formulations. Networks, 23:19– 28, 1993.
[14] F. K. Hwang, D. S. Richards, and P. Winter. The Steiner
Tree Problem. North-Holland, Amsterdam, 1992.
[15] S. Khuller. Design and Analysis of Algorithms. Lecture
Notes, University of Maryland, Department of Computer
Science, 1994. 112 pp.
[16] T. Koch and A. Martin. Solving Steiner Tree Problems in
Graphs to Optimality. Networks, 32:207–232, 1998.
[17] L. Kou, G. Markowsky, and L. Berman. A Fast Algorithms
for Steiner Trees. Acta Informatica, 15:141–145, 1981.
[18] Y.-C. Lin, H.-A. Chien, C.-C. Shih, and H.- M. Chen. A
Multi-layer Obstacles-Avoiding Router Using X-Architecture.
WSEAS Transactions on Circuits and Systems, 7:879–888,
2008.
[19] A. Lucena and J. E. Beasley. A Branch and Cut Algorithm
for the Steiner Problem in Graphs. Networks, 31:39–59, 1998.
[20] J. Plesn´ık. Grafov´e algoritmy. VEDA, vydavate´lstvo
Slovenskej akad´emie vied, Bratislava, 1983.
[21] J. Plesn´ık. Heuristics for the Steiner Problem in Graphs.
Discrete Applied Mathematics, 37/38:451–463, 1992.
[22] H. J. Pr¨omel and A. Steger. The Steiner Tree Problem. A
Tour through Graphs, Algorithms, and Complexity. Vieweg
Verlag, Braunschweig, 2002.
[23] G. Skorobohatyj. Testsets. Report, Konrad-Zuse-Zentrum
f¨ur Informationstechnik, Berlin, 2000.
ftp://ftp.zib.de/pub/Packages /mp-testdata/index.html.
[24] H. Takahashi and A. Matsuyama. An Approximate
Solution for the Steiner Problem in Graphs. Mathematica
Japonica, 24(6):573–577, 1980.
[25] D. H. Wolpert and W. G. McReady. No Free Lunch
Theorems for Optimization. IEEE Transactions on
Evolutionary Computation, 1(1):67–82, 1997.
[26] D. H. Wolpert and W. G. McReady. Coevolutionary Free
Lunches. IEEE Transactions on Evolutionary Computation,
9(6):721–735, 2005.
[27] P. ˇSeda, M. ˇSeda, and J. Hoˇsek. On Mathematical
Modelling of Automated Coverage Optimization in Wireless
5G and beyond Deployments. Applied Sciences, 10(24):1–25,
2020.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the Creative
Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en_US
WSEAS TRANSACTIONS on COMPUTERS
DOI: 10.37394/23205.2022.21.31