An Exact Algorithm for Steiner Tree Problem on Graphs

  • Milan Stanojevic University of Belgrade Faculty of Organizational Sciences Address: Jove Ili´ca 154, Belgrade, Serbia and Montenegro
  • Mirko Vujoševic University of Belgrade Faculty of Organizational Sciences Address: Jove Ili´ca 154, Belgrade, Serbia and Montenegro

Abstract

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

[1] 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.

[2] 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

[3] 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

[4] F. K. Hwang, D. S. Richards, "Steiner tree problems", Networks, Vol. 22, pp. 55-89, 1992.
http://dx.doi.org/10.1002/net.3230220105

[5] F. K. Hwang, D. S. Richards, P. Winter, The Steiner tree problem, North-Holland, Amsterdam, 1992.

[6] 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

[7] 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:3<207::AID-NET5>3.0.CO;2-O

[8] 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:1<39::AID-NET5>3.0.CO;2-L

[9] 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.

[10] 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.

[11] P. Winter, "Steiner problem in networks: A survey", Networks, Vol. 17, pp. 129-167, 1987.
http://dx.doi.org/10.1002/net.3230170203

[12] GNU Lesser General Public License, http://www.gnu.org/copyleft/lesser.html

[13] Lp_solve Reference Guide, http://www.geocities.com/lpsolve/

[14] SteinLib TestSets – The Library of Standard Steiner Problems, http://elib.zib.de/steinlib/testset.php

[15] STP – Description of the STP Data Format, http://elib.zib.de/steinlib/format.php
Published
2006-01-01
How to Cite
STANOJEVIC, Milan; VUJOŠEVIC, Mirko. An Exact Algorithm for Steiner Tree Problem on Graphs. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 1, n. 1, p. 41-46, jan. 2006. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2271>. Date accessed: 27 june 2022.

Keywords

Steiner tree problem on graph, branch and cut, algorithm, optimization