Heuristic algorithm for finding approximate solution of steiner problem based on physical analogies
A.V. Lisin, R.T. Faizullin

PDF, 1066 kB

Full text of article: Russian language.

DOI: 10.18287/0134-2452-2013-37-4-503-510

Pages: 503-510.

Abstract:
The article contains analyze of existent methods for solving Steiner problem that use physical analogies. Algorithm for construction of minimal Steiner trees based on existent solutions and Delaunay triangulation for initial approximation is suggested. Done comparison of suggested algorithm output and one with exponential complexity, which produces exact results.

Key words:
steiner problem, heuristic algorithm, Delaunay triangulation.

References:

  1. Courant, R. What is Mathematics / R. Courant, H. Robbins. – Oxford University Press, 1996. – 556 p.
  2. Hwang, F. The Steiner Tree Problem / F.K. Hwang, D.S. Richards, P. Winter // Annals of Discrete mathematics. – 1992. – Vol. 53.
  3. Yang, Z.-X. Geometry Experiment Algorithm Steiner Minimal Tree Problem / Z.-X. Yang, X.-Y. Kia, J.-Y. Hao, Y.-P. Gao // Journal of Applied Mathematics. – 2013. – Vol. 2013. – P. 1-10.
  4. Bogachenko, N.F. Mechanical analogies in Steiner problem / N.F. Bogachenko, R.T. Faizullin // Mathematical structures and modeling. – 2002. – Vol. 9. – P. 1-8. – (In Russian).
  5. Gilbert, E.N. Steiner Minimal Trees / E.N. Gilbert, H.O. Pol­lak // Journal on Applied Mathematics. – 1968. – Vol. 16. – P. 323-345.
  6. Cormen, T. Introduction to Algorithms, / T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. – 2nd edition. – Moscow: “Williams” Publisher, 2012. –1296 p. – (In Russian).
  7. Skvortsov, A.V. Delaunay Triangulation and its Applications / A.V. Skvortsov. – Tomsk: “Tomsk University Press” Publisher, 2002. – 128 p. – (In Russian).
  8. Marcelo, Z.N. An Interactive Pro-gramme for Steiner trees [Electronic resource]. URL: http://arxiv.org/abs/1210.7788 (accessed: 28.08.2013)
  9. Bern, M.W. The Shortest-Network Problem / M.W. Bern, R.L. Graham // In the World of Science. – 1989. – Vol. 3 – (In Russian).
  10. Du, D.Z. An approach for proving lower bounds: Solution of Gilbert–Pollak’s conjuncture on Steiner ratio. / D.Z. Du, F.K. Hwang // Proc. 31-st Annual Symp. On Found. Of Comput. Sci. – 1990. – P. 76-85.
© 2009, IPSI RAS
Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; e-mail: ko@smr.ru; Phones: +7 (846 2) 332-56-22, Fax: +7 (846 2) 332-56-20