CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Fast reoptimization of Steiner trees: Changing the Edge set

by Subhash Panwar, Suneeta Agarwal
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 1 - Number 28
Year of Publication: 2010
Authors: Subhash Panwar, Suneeta Agarwal
10.5120/517-834

Subhash Panwar, Suneeta Agarwal . Fast reoptimization of Steiner trees: Changing the Edge set. International Journal of Computer Applications. 1, 28 ( February 2010), 22-24. DOI=10.5120/517-834

@article{ 10.5120/517-834,
author = { Subhash Panwar, Suneeta Agarwal },
title = { Fast reoptimization of Steiner trees: Changing the Edge set },
journal = { International Journal of Computer Applications },
issue_date = { February 2010 },
volume = { 1 },
number = { 28 },
month = { February },
year = { 2010 },
issn = { 0975-8887 },
pages = { 22-24 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume1/number28/517-834/ },
doi = { 10.5120/517-834 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T19:49:18.460371+05:30
%A Subhash Panwar
%A Suneeta Agarwal
%T Fast reoptimization of Steiner trees: Changing the Edge set
%J International Journal of Computer Applications
%@ 0975-8887
%V 1
%N 28
%P 22-24
%D 2010
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, we discuss the problem of reoptimization of Steiner tree. We are given an instance of Graph and also an optimal Steiner tree of it. If some changes occurs later on in the given graph. New optimal Steiner tree is to be determine, this process is known as re optimization. We consider two cases of change: one is addition of a new edge and second is, Deletion of an existing edge. For both the cases, we provide approximation algorithms with corresponding approximation ratio equal to (1+d) where 0

References
  1. Bang Ye Wu and Kun-Mao Chao, Spanning tree and optimization problem, in Chapman & Hall/CRC Press,USA,2004.
  2. F. Hwang, D.Richards, P.Winter The Steiner tree problem, in Annals of Discrete Mathematics,Vol.53 North-Holland,1992.
  3. B. Escoffier, M. Milanic, V.T. Paschos, Simple and fast reoptimizations of Steiner tree problem. DIMACS Techn. Report 2007-01, 2007.
  4. S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1:195-207, 1972.
  5. Bil`o, D., B¨ockenhauer, H.-J., Hromkovi?c, J., Kr´alovi?c, R., M¨omke, T., Widmayer, P., Zych, A.: Reoptimization of Steiner trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 258-269. Springer, Heidelberg (2008)
  6. Cs0821 Sa120976
  7. B¨ockenhauer, H.-J., Hromkovi?c, J., Kr´alovi?c, R., M¨omke, T., Rossmanith, P.: Reoptimization of Steiner trees: Changing the terminal set. Theoretical Computer Science.
  8. D.B. West, Introduction to Graph Theory, 2nd edn, Prentice Hall Inc., Upper Saddle River, NJ, 2000.
  9. Pr¨omel, H.J., Steger, A.: The Steiner Tree Problem. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig (2002)
Index Terms

Computer Science
Information Sciences

Keywords

Steiner tree approximation algorithm reoptimization

Powered by PhDFocusTM