A subset spanner for planar graphs, with application to subset TSP. (English) Zbl 1301.05335
Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 749-756 (2006).
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W25 | Approximation algorithms |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | U. A. Acar, G. E. Blelloch, R. Harper, J. L. Vittes, and S. L. M. Woo, “Dynamizing static algorithms, with applications to dynamic trees and history independence,” Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 531-540, 2004]] · Zbl 1318.68080 |
| [2] | S. Alstrup, J. Holm, K. D. Lichtenberg, and M. Thorup. “Maintaining information in fully-dynamic trees with top trees,” ACM Transactions on Algorithms 1(2), pp. 243-264, 2005.]] 10.1145/1103963.1103966 · Zbl 1321.68211 |
| [3] | I. Althöfer, G. Das, D. Dobkin, D. Joseph, L. Soares, “On sparse spanners of weighted graphs,” Discrete and Computational Geometry, 9, pp. 81-100, 1993.]] · Zbl 0762.05039 |
| [4] | S. Arora, “Polynomial-time approximation schemes for Euclidean TSP and other geometric problems,” Journal of the ACM 45, pp. 753-782, 1998.]] 10.1145/290179.290180 · Zbl 1064.90566 |
| [5] | S. Arora, M. Grigni, D. R. Karger, P. N. Klein, A. Woloszyn, “ A polynomial-time approximation scheme for weighted planar graph TSP,” Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 33-41, 1998.]] · Zbl 0930.68104 |
| [6] | R. F. Cohen, R. Tamassia, “Combine and Conquer,” Algorithmica 18(3), pp. 324-362 (1997).]] |
| [7] | G. Das and D. Joseph, “Which triangulations approximate the complete graph?” Proceedings of the International Symposium on Optimal Algorithms, Springer LNCS 401, pp. 168-192, 1989.]] · Zbl 0704.68087 |
| [8] | G. Das, G. Narasimhan, and J. S. Salowe, “A new way to weight malnourished Euclidean graphs,” Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 215-222, 1995.]] · Zbl 0849.68090 |
| [9] | E. D. Demaine, M. Hajiaghayi, “Bidimensionality: new connections between FPT algorithms and PTASs,” Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 590-601, 2005.]] · Zbl 1297.05056 |
| [10] | G. N. Frederickson, “Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees,” SIAM J. Comput 26 (1997), pp. 484-538.]] 10.1137/S0097539792226825 · Zbl 0874.68081 |
| [11] | M. Grigni, E. Koutsoupias, and C. H. Papadimitriou, “An approximation scheme for planar graph TSP,” Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp 640-645, 1995.]] · Zbl 0938.68748 |
| [12] | M. Grigni, “Approximate TSP in graphs with forbidden minors,” Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, pp. 869-877, 2000.]] · Zbl 0973.68263 |
| [13] | P. N. Klein, “Preprocessing an undirected planar network to enable fast approximate distance queries,” Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Algorithms, pages 820-827, 2002.]] · Zbl 1093.68622 |
| [14] | P. N. Klein, “Multiple-source shortest paths in planar graphs,” Proceedings of the Sixteenth ACM-SIAM Symposium on Discrete Algorithms, pp. 146-155, 2005.]] · Zbl 1297.05059 |
| [15] | P. N. Klein, “A linear-time approximation scheme for planar weighted tsp,” IEEE Symposium on Foundations of Computer Science, pp. 647-656, 2005.]] 10.1109/SFCS.2005.7 |
| [16] | C. Levcopoulos and A. Lingas, “There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees,” Proceedings of the International Symposium on Optimal Algorithms, Springer LNCS 401, pp. 9-13, 1989.]] · Zbl 0704.68088 |
| [17] | J. Mitchell, “Guillotine subdivisions approximate polygonal subdivisions: Part II– a simple PTAS for geometric k-MST, TSP, and related problems,” SIAM Journal on Computing 28, pp. 298-1309, 1999.]] 10.1137/S0097539796309764 · Zbl 0940.68062 |
| [18] | K. Mehlhorn, “A faster approximation algorithm for the Steiner problem in graphs,” Information Processing Letters 27(3), pp. 125-128, 1988.]] 10.1016/0020-0190(88)90066-X · Zbl 0635.68071 |
| [19] | C. H. Papadimitriou and M. Yannakakis, “The traveling salesman problem with distances one and two,” Mathematics of Operations Research, 18(1), pp. 1-11, 1993.]] · Zbl 0778.90057 |
| [20] | S. B. Rao and W. D. Smith, “Approximating geometrical graphs via ”spanners’ and ’banyans’,” Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 540-550, 1998.]] 10.1145/276698.276868 · Zbl 1027.68651 |
| [21] | D. D. Sleator and R. E. Tarjan, “A data structure for dynamic trees,” Journal of Computer and System Sciences, 26(3), pp. 362-391, 1983.]] 10.1016/0022-0000(83)90006-5 · Zbl 0509.68058 |
| [22] | M. Thorup, “Compact oracles for reachability and approximate distances in planar digraphs,” Journal of the ACM 51(6), pp. 993-1024, 2004.]] 10.1145/1039488.1039493 · Zbl 1125.68394 |
| [23] | R. E. Tarjan and R. F. Werneck, “Self-adjusting top trees,” Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 813-822, 2005.]] · Zbl 1297.68069 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
