4551
правка
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
→См. также
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Разработка алгоритма аппроксимации == Определение == Пусть…») |
Irina (обсуждение | вклад) |
||
| Строка 143: | Строка 143: | ||
== См. также == | == См. также == | ||
'' | * ''[[Алгоритмы жадной аппроксимации]] | ||
* ''[[Минимальные остовные деревья]] | |||
* ''Прямолинейное дерево Штейнера]] | |||
Литература | |||
== Литература == | |||
1. Arora, S.: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Proc. 37th IEEE Symp. on Foundations of Computer Science, pp. 2-12 (1996) | 1. Arora, S.: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Proc. 37th IEEE Symp. on Foundations of Computer Science, pp. 2-12 (1996) | ||
2. Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. J. Algorithms 17, 381^08(1994) | 2. Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. J. Algorithms 17, 381^08(1994) | ||
3. Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32,171 -176 (1989) | 3. Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32,171 -176 (1989) | ||
4. Chang, S.K.: The generation of minimal trees with a Steiner topology. J.ACM 19,699-711 (1972) | 4. Chang, S.K.: The generation of minimal trees with a Steiner topology. J.ACM 19,699-711 (1972) | ||
5. Chang, S.K.: The design of network configurations with linear or piecewise linear cost functions. In: Symp. on Computer-Communications, Networks, and Teletraffic, pp. 363-369 IEEE Computer Society Press, California (1972) | 5. Chang, S.K.: The design of network configurations with linear or piecewise linear cost functions. In: Symp. on Computer-Communications, Networks, and Teletraffic, pp. 363-369 IEEE Computer Society Press, California (1972) | ||
6. Crourant, R., Robbins, H.: What Is Mathematics? Oxford University Press, New York (1941) | 6. Crourant, R., Robbins, H.: What Is Mathematics? Oxford University Press, New York (1941) | ||
7. Du, D.Z., Hwang, F.K.: The Steiner ratio conjecture of Gilbert-Pollak is true. Proc. Natl. Acad. Sci. USA 87,9464-9466 (1990) | 7. Du, D.Z., Hwang, F.K.: The Steiner ratio conjecture of Gilbert-Pollak is true. Proc. Natl. Acad. Sci. USA 87,9464-9466 (1990) | ||
8. Du, D.Z., Zhang, Y., Feng, Q.: On better heuristic for euclidean Steiner minimum trees. In: Proceedings 32nd FOCS, IEEE Computer Society Press, California (1991) | 8. Du, D.Z., Zhang, Y., Feng, Q.: On better heuristic for euclidean Steiner minimum trees. In: Proceedings 32nd FOCS, IEEE Computer Society Press, California (1991) | ||
9. Du, D.Z., Graham, R.L., Pardalos, P.M., Wan, P.J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167-175. ACM, New York (2008) | 9. Du, D.Z., Graham, R.L., Pardalos, P.M., Wan, P.J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167-175. ACM, New York (2008) | ||
10. Kahng, A., Robins, G.: A new family of Steiner tree heuristics with good performance: the iterated 1-Steiner approach. In: Proceedings of IEEE Int. Conf. on Computer-Aided Design, Santa Clara, pp.428-431 (1990) | 10. Kahng, A., Robins, G.: A new family of Steiner tree heuristics with good performance: the iterated 1-Steiner approach. In: Proceedings of IEEE Int. Conf. on Computer-Aided Design, Santa Clara, pp.428-431 (1990) | ||
11. Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385-393 (1982) | 11. Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385-393 (1982) | ||
12. Robin, G., Zelikovsky, A.: Improved Steiner trees approximation in graphs. In: SIAM-ACM Symposium on Discrete Algorithms (SODA), San Francisco, CA, pp. 770-779. January (2000) | 12. Robin, G., Zelikovsky, A.: Improved Steiner trees approximation in graphs. In: SIAM-ACM Symposium on Discrete Algorithms (SODA), San Francisco, CA, pp. 770-779. January (2000) | ||
13. Smith, J.M., Lee, D.T., Liebman, J.S.: An O(N log N) heuristic for Steiner minimal tree problems in the Euclidean metric. Networks 11, 23-39 (1981) | 13. Smith, J.M., Lee, D.T., Liebman, J.S.: An O(N log N) heuristic for Steiner minimal tree problems in the Euclidean metric. Networks 11, 23-39 (1981) | ||
14. Zelikovsky, A.Z.: The 11/6-approximation algorithm for the Steiner problem on networks. Algorithmica 9,463^70 (1993) | 14. Zelikovsky, A.Z.: The 11/6-approximation algorithm for the Steiner problem on networks. Algorithmica 9,463^70 (1993) | ||