A 1.598 approximation algorithm for the Steiner problem in graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A 1.598 approximation algorithm for the Steiner problem in graphs

Full text

Pdf (515 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 448 - 453

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

Stefan Hougardy	Humboldt-Universität zu Berlin, Institut für Informatik, 10099 Berlin, Germany
Hans Jürgen Prömel	Humboldt-Universität zu Berlin, Institut für Informatik, 10099 Berlin, Germany

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 54, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
	2	S. Arora, C. Lund, R. Motwemi, M. Sudan and M.Szegedy, Proof verification and hardness of approzimotion problems, Proceedings 33rd Annual Symposium on Foundations of Computer Science (1992), 14-23.
	3	Sanjeev Arora , Michelangelo Grigni , David Karger , Philip Klein , Andrzej Woloszyn, A polynomial-time approximation scheme for weighted planar graph TSP, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.33-41, January 25-27, 1998, San Francisco, California, United States
	4	Piotr Berman , Viswanathan Ramaiyer, Improved approximations for the Steiner tree problem, Journal of Algorithms, v.17 n.3, p.381-408, Nov. 1994
	5	Al Borchers , Ding-Zhu Du, The k-Steiner Ratio in Graphs, SIAM Journal on Computing, v.26 n.3, p.857-869, June 1997 [doi>10.1137/S0097539795281086]
	6	Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2]
	7	Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
	8	A.E.F.Clementi and L.Trevisem, Improved nonapprozimability results for minimum vertez cover with density constraints, Electronic Colloquium on Computational Complexity, TR96-016, (1996).
	9	Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
	10	M. Kaxpinski and A. Zelikovsky, New approximation algorithms for the Steiner tree problems, Journal of Combinatorial Optimization 1 (1997), 47-65.
	11	Hans Jürgen Prömel , Angelika Steger, RNC-Approximation Algorithms for the Steiner Problem, Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.559-570, February 27-March 01, 1997
	12	H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Jap. 24 (1980), 573-577.
	13	A. Zelikovsky, An ll//6-approximation algorithm for the network Steiner problem, Algorithmica 9 (1993), 463-470.
	14	Alexander Zelikovsky, Better approximation bounds for the network and Euclidean Steiner tree problems, University of Virginia, Charlottesville, VA, 1996

CITED BY 9

	Martin Thimm, On the approximability of the Steiner tree problem, Theoretical Computer Science, v.295 n.1-3, p.387-402, 24 February 2003
	Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
	Guohui Lin , Guoliang Xue, On the terminal Steiner tree problem, Information Processing Letters, v.84 n.2, p.103-107, 31 October 2002
	Clemens Gröpl , Stefan Hougardy , Till Nierhoff , Hans Jürgen Prömel, Steiner trees in uniformly quasi-bipartite graphs, Information Processing Letters, v.83 n.4, p.195-200, 31 August 2002
	Kamal Jain , Mohammad Mahdian , Mohammad R. Salavatipour, Packing Steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Sun-Yuan Hsieh , Huang-Ming Gao, On the partial terminal Steiner tree problem, The Journal of Supercomputing, v.41 n.1, p.41-52, July 2007
	Yehuda Ben-Shimol , Boaz Ben-Moshe , Yoav Ben-Yehezkel , Amit Dvir , Michael Segal, Automated antenna positioning algorithms for wireless fixed-access networks, Journal of Heuristics, v.13 n.3, p.243-263, June 2007
	Sun-Yuan Hsieh , Shih-Cheng Yang, Note: Approximating the selected-internal Steiner tree, Theoretical Computer Science, v.381 n.1-3, p.288-291, August, 2007
	Glencora Borradaile , Philip Klein , Claire Mathieu, An O(n log n) approximation scheme for Steiner tree in planar graphs, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-31, July 2009