When trees collide

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

When trees collide: an approximation algorithm for the generalized Steiner problem on networks

Full text

Pdf (1.12 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 134 - 144

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Ajit Agrawal	Brown Univ., Providence, RI
Philip Klein	Brown Univ., Providence, RI
R. Ravi	Brown Univ., Providence, RI

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/103418.103437 What is a DOI?

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	Y. P. Aneja, "An integer linear programming approach to the Steiner problem in graphs', Networks, vol. 10 (1980) 167-178.
	2	Charles J. Colbourn, Edge-packing of graphs and network reliability, Discrete Mathematics, v.72 n.1-3, p.49-61, December 1988 [doi>10.1016/0012-365X(88)90193-8]
	3	J. Edmonds, and E. L. Johnson, "Matching, Euler tours and the Chinese postman", Math. Programming, vol. 5 (#973) pp. 88-124.
	4	C. E1-Arbi, "One heuristique pour le problem de l'arbre de Steiner", R.A.LR.O. Operations Research, vol. 15 (1978), pp. 207-212.
	5	M. X. Goemans, and D. J. Bertsimas, "Survivable Networks, Linear Programming Relaxations and the Parsimonious Property", OR 216-90, Center for Operations B.esearch, MIT (1990).
	6	A. J a in, "Probabilistic analysis of an LP relaxation bound for the Steiner problem in networks", Networks, vol. 19 (1989), pp. T93-80#.
	7	R. M. Karp, "Reducibility among combinatorial problems", in R. E. Miller and 3. W. Thatcher (eds.), Complexity of Computer Computations. Plenum Press, New York (1972) pp. ss-10s.
	8	P. N. Klein, A. Agrawal, R. Ravi, and S. Rao, "Approximation through multicommodity flow", 31st Annual Syrup. on Foundations o.f Comp. Sci., (1990), pp. 726-737.
	9	L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees", Acts Informatica, vol. 15 (1981), pp. 141-145.
	10	L. Ldvasz, "An algorithmic theory of numbers, graphs and convexity". SIAM, Philadelphia (1986).
	11	M. Minoux, "Network synthesis and optimum network design problems: models, solution methods and applications", Networks, vol. 19 (1989) pp. 313-360.
	12	3. Plesnik, "A bound for the Steiner tree problem in graphs", Math. Slovaca, vol. 31 (1981) pp. 155-163.
	13	V.J. Rayward-Smith, "The computation of nearly minimal Steiner trees in graphs", Int. J. Math. Educ. Sci. Tech., vol. 14 (1983), pp. 15-23.
	14	A. Segev, The node-weighted Steiner tree problem, Networks, v.17 n.1, p.1-17, Spring 1987 [doi>10.1002/net.3230170102]
	15	G. F. Sullivan, "Approximation algorithms for Steiner tree problems", Tech. Rep. 249, Dept. of Comp. Sci., Yale Univ. (1982).
	16	Hitoshi Suzuki , Takehiro Akama , Takao Nishizeki, Finding Steiner forests in planar graphs, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.444-453, January 22-24, 1990, San Francisco, California, United States
	17	H. Takahashi, and A. Matsuyama, " An approximate solution for the Steiner problem in graphs", Math. Japonica, vol. $# (1980) pp. 573-577.
	18	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	19	L. G. Valiant, "The complexity of enumeration and reliability problems", Siam J. Comput., vol. 8 (1979), pp. 410-421.
	20	Pawel Winter, Generalized Steiner problem in outerplanar networks, BIT, v.25 n.3, p.485-496, 1985 [doi>10.1007/BF01935369]
	21	P. Winter, Steiner problem in networks: a survey, Networks, v.17 n.2, p.129-167, Summer 1987 [doi>10.1002/net.3230170203]
	22	R. T. Wong, "Worst-case analysis of network design problem heuristics", SIAM J. Alg. Disc. Math., vol. i (1980), pp. 51-63.
	23	R. T. Wong, "A dual ascent approach for Steiner tree problems on a directed graph", Math. Program., vol. $8, (1984) pp. 271-287.

CITED BY 16

	R. Ravi , M. V. Marathe , S. S. Ravi , D. J. Rosenkrantz , H. B. Hunt, III, Many birds with one stone: multi-objective approximation algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.438-447, May 16-18, 1993, San Diego, California, United States
	R. Ravi , David P. Williamson, An approximation algorithm for minimum-cost vertex-connectivity problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.332-341, January 22-24, 1995, San Francisco, California, United States
	Martin Fürer , Balaji Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.317-324, September 1992, Orlando, Florida, United States
	Michel X. Goemans , David P. Williamson, A general approximation technique for constrained forest problems, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.307-316, September 1992, Orlando, Florida, United States
	Sanjeev Khanna , Joseph Naor , F. Bruce Shepherd, Directed network design with orientation constraints, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.663-671, January 09-11, 2000, San Francisco, California, United States
	Manica Aggarwal , Naveen Garg, A scaling technique for better network design, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.233-240, January 23-25, 1994, Arlington, Virginia, United States
	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
	David P. Williamson , Michel X. Goemans , Milena Mihail , Vijay V. Vazirani, A primal-dual approximation algorithm for generalized Steiner network problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.708-717, May 16-18, 1993, San Diego, California, United States
	Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
	M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
	Piotr Berman , Chris Coulston, On-line algorithms for Steiner tree problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.344-353, May 04-06, 1997, El Paso, Texas, United States
	Richard Cole , Ramesh Hariharan, A fast algorithm for computing steiner edge connectivity, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Samir Khuller , Balaji Raghavachari , Neal E. Young, Approximating the minimum equivalent digraph, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.177-186, January 23-25, 1994, Arlington, Virginia, United States
	Jochen Könemann , R. Ravi, Primal-dual meets local search: approximating MST's with nonuniform degree bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Sanjeev Arora , Satyen Kale, A combinatorial, primal-dual approach to semidefinite programs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Lap Chi Lau , Mohit Singh, Additive approximation for bounded degree survivable network design, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada