4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 16:58, 17 октября 2016
, 17 октября 2016→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 94: | Строка 94: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Остаются нерешенными две задачи. | |||
1. Улучшение объема используемой структурой данных оракула расстояния памяти – с O(n log n) до O(n). | |||
2. Расширение структуры данных оракула расстояния, позволяющее выдавать не только приблизительное расстояние, но и приблизительный кратчайший путь между заданными в запросе точками. | |||
== См. также == | |||
*' [[Алгоритм поиска кратчайших путей в разреженных графах]] | |||
*' [[Алгоритм поиска кратчайших путей при помощи матричного произведения]] | |||
*' [[Геометрические остовы]] | |||
*' [[Планарные геометрические остовы]] | |||
*' [[Разреженные остовы графов]] | |||
*' [[Синхронизаторы, остовы]] | |||
== Литература == | |||
1. Agarwal, P.K., Har-Peled, S., Karia, M.: Computing approximate shortest paths on convex polytopes. In: Proceedings of the 16th ACM Symposium on Computational Geometry, pp. 270-279. ACM Press, New York (2000) | |||
2. Arikati, S., Chen, D.Z., Chew, L.P., Das, G., Smid, M., Zaroliagis, C.D.: Planar spanners and approximate shortest path queries among obstacles in the plane. In: Proceedings of the 4th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 1136, Berlin, pp. 514-528. Springer, London (1996) | |||
3. Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in 6(n2) time. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 271-280. ACM Press, New York (2004) | |||
4. Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of the4th Latin American Symposium on Theoretical Informatics. Lecture Notes in Computer Science, vol. 1776, Berlin, pp. 88-94. Springer, London (2000) | |||
5. Chen, D.Z., Daescu, O., Klenk, K.S.: On geometric path query problems. Int. J. Comput. Geom. Appl. 11,617-645 (2001) | |||
6. Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Int. J. Comput. Geom. Appl. 7,297-315(1997) | |||
7. Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Discrete mobile centers. Discrete Comput. Geom. 30,45-63 (2003) | |||
8. Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Fast greedy algorithms for constructing sparse geometric spanners. SIAM J. Comput. 31,1479-1500 (2002) | |||
9. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric graphs. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828-837. ACM Press, New York (2002) | |||
10. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles revisited. In: Proceedings of the 13th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2518, Berlin, pp. 357-368. Springer, London (2002) | |||
11. Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric spanners, ACM Trans. Algorithms (2008). To Appear | |||
12. Gudmundsson, J., Narasimhan, G., Smid, M.: Fast pruning of geometric spanners. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 3404, Berlin, pp. 508-520. Springer, London (2005) | |||
13. Narasimhan, G., Smid, M.: Geometric Spanner Networks, Cambridge University Press, Cambridge, UK (2007) | |||
14. Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51,993-1024 (2004) | |||
15. Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, pp. 183-192. ACM Press, New York (2001) | |||