The week's pick
Random Articles
Reseach Article
Steiner Path for Trees
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 76 - Number 5 |
| Year of Publication: 2013 |
| Authors: Shanti Swaroop Moharana, Ankit Joshi, Swapnil Vijay |
10.5120/13242-0692
|
Shanti Swaroop Moharana, Ankit Joshi, Swapnil Vijay . Steiner Path for Trees. International Journal of Computer Applications. 76, 5 ( August 2013), 11-14. DOI=10.5120/13242-0692
Abstract
The Steiner minimum tree (SMT) problem is one of the classic nonlinear combinatorial optimization problems for centuries. The Steiner tree problem finds the minimum cost tree connecting a given set of nodes called required nodes in a given undirected weighted graph. In this minimum cost Steiner tree due to the reduction of path-cost, some non-required nodes are also used while finding the SMT, which are called Steiner nodes. The Steiner path problem comes from the Steiner tree problem of finding the minimum cost path connecting a given set of nodes called required nodes in a given undirected weighted graph. The Steiner path problem can be characterized as either a decision or optimization problem. This paper focuses on solving the Steiner path as a decision problem. The Steiner Path decision problem finds whether there is a path connecting a given set of nodes called required nodes in a given binary tree. The decision that whether there exists a Steiner path or not can help in further solving the Steiner path optimization problem. Since the Steiner tree decision problem has wide scales, we should use an efficient algorithm with least complexity. In this paper we have defined the steiner path decision problem, characterized sufficient conditions for finding the steiner path and presented an algorithm for finding the existence of a steiner path in a 2-tree.
References
- Hwang F K, Richard D S. Steiner tree problems. Networks, 1992, 22(1):55-89
- Winter P. Steiner problem in networks: a survey J. Networks l987, 17:129-167
- Gilbert E N, Pollak H O. Steiner minimal tree. SIAN J. pp. Math, 1968(16):1-29
- Du D Z, Hwang F K. "The Steiner ration conjecture of Gilbert" New York: 1992; 7(1):121-135
- R. M. Karp, "Reducibility among combinatorial problems", Complexity of Computer Communications, R. E. Miller and J. W. Thatcher (Eds. ), Plenum Press, New York, pp. 85-103, 1972.
- M. Tashakkori, P. Adibi, A. Jahanian, A. Nourollah, "Ant colony solution dynamic Steiner tree problem", Proceedings of 9th Annual Computer Society of Iran Computer Conference, pp. 465-471, 2003
- W. Q. Yang, T. D. Guo, An ant colony optimization algorithm for the minimum Steiner tree problem and its convergence proof. Acta Mathematicae Applicatae Sinica, 2006, Vol. 29, No. 2, pp. 352-361(in Chinese).
- Luc Luyet, Sacha Varone, and Nicolas Zufferey: "An ant algorithm for the Steiner tree problem in graphs. " 2007.
- Hui-min JIN, Liang MA, Zhou-mian WANG. "Intelligent Optimization Algorithms for Euclidean Steiner Minimum Tree Problem" J. Computer Engineering. 2006, 32(10):201-203.
- Takahashi H, Matsuyama A. "An approximate solution for the Steiner program in graphs" J. Math Japonica, 1980. 24:537-577
- Fatemeh Ghadimi, Ali Nourollah "A Heuristic Algorithm for Solving Steiner Tree Problem on Urban Traffic Network" May 15-17,2012, ICEE2012, Tehran, Iran
- Narendra Maharjan, Abinash Shrestha, Ashish Tamrakar and Sanjeeb Prasad Panday "Solving Minimum Steiner tree based on behavior of ants" 978-1-4673-2590-5/12/ IEEE
- A. Karim Abu-Aash, Paz Carmi, Matthew J. Katz, Michael Segal "The Euclidean Bottleneck Steiner Path Problem" Proceedings of the 27th annual ACM symposium on Computational geometry pp. 440-447
Index Terms
Keywords