Satish B. Rao
Warren D. Smith
- 1.S. Arora. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In Proceedings of the 33th Annual Symposium on Foundations of Computer Science, 1997. Also available electronically on Arora's web page http://wwa, cs. princeton, edu/~axora/publist, html in an updated form. Google Scholar
Digital Library
- 2.S. Arya, G.Das, D.M.Mount, J.S.Salowe, and M.Smid. Euclidean spanners: short, thin, and lanky. In Proceedings of the ~Tth Annual A CM Symposium on Theory of Computing, pages 489-498, 1995. Google ScholarDigital Library
- 3.J.E. Beasley and F.Goffmet. A Delaunay triangulationbased heuristic for the Euclidean Steiner problem. Networks, pages 215-224, 1994.Google Scholar
- 4.B.M. Chazelle. A faster deterministic algorithm for minimum spanning trees. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 22-34, 1997. Google ScholarDigital Library
- 5.N. Christophides. Worst-case analysis of a new heuristic for the traveling salesman problem. In J.F.Traub, editor, Symposium on new directions and recent reaults in algorithms and complexity. Academic Press, 1976.Google Scholar
- 6.G. Das, S. Kapoor, and M. Staid. On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees. Algorithmica, 19:447-460, 1997.Google ScholarCross Ref
- 7.G. Das, G. Naxasimhan, and J. Salowe. A new way to weigh malnourished Euclidean graphs. In Proceedings of the 6th Annual A CM-SIAM Symposium on Discrete Algorithms, pages 215-222, 1995. Google ScholarDigital Library
- 8.D. Z. Du and F. K. Hwang. A proof of the Gilbert-Pollal: conjecture on the Steiner ratio. Algorithmica, 7:121-135, 1992.Google ScholarCross Ref
- 9.E.Aarts and J.K.Lenstra, editors. Local search in com. binatorial optimization. J.Wiley, 1997. Google ScholarDigital Library
- 10.U. FSssmeier and M. Kaufmann. Solving rectilinear Steiner tree problems exactly in theory and practice. 1997. Google ScholarDigital Library
- 11.M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SiAM J. Appl. Math., 32(4):835-859, 1977.Google ScholarDigital Library
- 12.E.N. Gilbert and H.O. Pollak. Steiner minimal trees. SIAM J. Appl. Math., 16(1):1-29, 1968.Google ScholarDigital Library
- 13.Michel X. Goemans. Worst-case comparison of valid inequalities for the TSP. Mathematical Programming, 69:335-349, 1995. Google ScholarDigital Library
- 14.M. Held and R.M. Karp. The traveling salesman problem and minimum spanning trees. Operations Research, 18:1138-1162, 1970.Google ScholarDigital Library
- 15.F.K. Hwang. On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math., 30(1):104-114, 1976.Google ScholarDigital Library
- 16.R.M. Karp. Probabilistic analysis of partitioning algorithms for the TSP in the plane. Math. Oper. Rca., 2:209- 224, 1977.Google ScholarDigital Library
- 17.E.L. Lawler, j.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, editors. The traveling salesman problem. j.Wiley, 1985.Google Scholar
- 18.J. Van Leeuwen and A.A. Schoone. Untangling a traveling salesman tour in the plane. In Proc. 7th conf. on graphtheoretic concepts in computer sci. (WG 81)~ Linz, Austria, pages 87-98, 1981.Google Scholar
- 19.S. Lin and B. Kernighan. An effective heuristic algorithm for the travelling-salesman problem. Operations Research, 21:498-516, 1973.Google ScholarDigital Library
- 20.M. Padberg and G. Rinaldi. A branch and cut algorithm for the resolution of large scale symmetric traveling salesman problems. SIAM Review, 33:60-100, 1991. Google ScholarDigital Library
- 21.Christos H. Papadimitriou. The complexity of the Lin- Kernighan heuristic for the traveling salesman problem. SIAM J. Comput., 21(3):450-465, 1992. Google ScholarDigital Library
- 22.D.B. Shmoys and D.P. Williamson. Analyzing the Held- Karp TSP bound: A monotonicity property with application. Into. Proc. Left., pages 281-285, 1990. Google ScholarDigital Library
- 23.W.D. Smith. Studies in computational geometry motivated by mesh generation. PhD thesis, Princeton Applied Math Dept., Princeton, NJ, 1988. University Microfilms International, order ~ 9002713. Google ScholarDigital Library
- 24.W.D. Smith. How to find Steiner minimal trees in dspace. Algorithmica, 7:137-177, 1992.Google ScholarCross Ref
- 25.Luca Trevisan. When Hamming meets Euclid: the approximability of geometric TSP and MST. In Proceedings of the ~9th Annual A CM Symposium on Theory of Computing, pages 21-29, 1997. Google ScholarDigital Library
- 26.David M. Warme. A new exact algorithm for rectilinear steiner trees. In International Symposium on Mathematical Programming, Lausanne, Switzerland, 1997.Google Scholar
- 27.P. Winter and M. Zachariasen. Euclidean Steiner minimal trees, an improved exact algorithm. Networka, 30(3):149-166, 1997.Google ScholarCross Ref
Index Terms
- Approximating geometrical graphs via “spanners” and “banyans”
Recommendations
Tree spanners on chordal graphs: complexity and algorithms
A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The TREE t-SPANNER problem asks whether a graph admits a tree t-spanner, given t. We substantially ...
Fault-tolerant spanners for general graphs
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingThe paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δH(u,v) ≤ k· δG(u,...
Comments