An Exact Algorithm for Steiner Tree Problem on Graphs
Keywords:
Steiner tree problem on graph, branch and cut, algorithm, optimizationAbstract
The paper presents a new original algorithm for solving Steiner tree problem on graph. The algorithm is simple and intended for solving problems with relatively low dimensions. It is based on use of existing open source software for solving integer linear programming problems. The algorithm is tested and shown very efficient for different randomly generated problems on graphs of up to 50 nodes, up to 10 terminals and average node degree 7.References
M. Berkelaar, K. Eikland, P. Notebaert, Lp_solve, Files and Discussion Group, ftp://ftp.es.ele.tue.nl/pub/lp_solve, http://groups.yahoo.com/group/lp_solve/, 1994-2006.
S. Chopra, E. Gorres, M. R. Rao, "Solving a Steiner tree problem on a graph using branch and cut", ORSA Journal on Computing, Vol. 4, pp. 320-335, 1992. http://dx.doi.org/10.1287/ijoc.4.3.320
G. B. Dantzig, D. R. Fulkerson, S. M. Johnson, "Solution of a large-scale traveling-salesman problem", Operations Research, Vol. 2, pp. 393-410, 1954. http://dx.doi.org/10.1287/opre.2.4.393
F. K. Hwang, D. S. Richards, "Steiner tree problems", Networks, Vol. 22, pp. 55-89, 1992. http://dx.doi.org/10.1002/net.3230220105
F. K. Hwang, D. S. Richards, P. Winter, The Steiner tree problem, North-Holland, Amsterdam, 1992.
R. M. Karp, "Reducibility among combinatorial problems", R. E. Miller, J. W. Thatcher (Ed.), Complexity of Computer Computations, pp. 85-103, Plenum Press, New York, 1972. http://dx.doi.org/10.1007/978-1-4684-2001-2_9
T. Koch, A. Martin, "Solving Steiner tree problems in graphs to optimality", Networks, Vol. 32, pp. 207-232, 1998. http://dx.doi.org/10.1002/(SICI)1097-0037(199810)32:33.0.CO;2-O
A. Lucena, J.E. Beasley, "A branch and cut algorithm for the Steiner problem in graphs", Networks, Vol. 31, pp. 39-59, 1998. http://dx.doi.org/10.1002/(SICI)1097-0037(199801)31:13.0.CO;2-L
N. Maculan, "The Steiner tree problem in graphs", Surveys in Combinatorial Optimization, S. Martello, G. Laporte, M. Minoux, C. C. Ribeiro (Ed.), Annals of Discrete Mathematics, Vol. 31, pp. 185-212, 1987.
M. Stanojevi´c, M. Vujoševi´c, "A new algorithm for solving Steiner tree problem on graph" (in Serbian), 12th Telecommunications Forum TELFOR 2004, Belgrade, http://www.telfor.org.yu/telfor2004/e-index.html (http://www.telfor.org.yu/telfor2004/radovi/TM-2-4.pdf), 2004.
P. Winter, "Steiner problem in networks: A survey", Networks, Vol. 17, pp. 129-167, 1987. http://dx.doi.org/10.1002/net.3230170203
GNU Lesser General Public License, http://www.gnu.org/copyleft/lesser.html
Lp_solve Reference Guide, http://www.geocities.com/lpsolve/
SteinLib TestSets - The Library of Standard Steiner Problems, http://elib.zib.de/steinlib/testset.php
STP - Description of the STP Data Format, http://elib.zib.de/steinlib/format.php
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
