Алгоритмы поиска остова во взвешенном графе: различия между версиями

Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 5: Строка 5:
== Постановка задачи ==
== Постановка задачи ==


[[Остов]] – это ''разреженный'' подграф данного неориентированного графа, сохраняющий приближенные расстояния между каждой парой вершин. Более точно, t-остов графа G = (V, E) представляет собой подграф (V, E<math>_{s}</math>), <math>E_{s} \subseteq E</math>, такой, что для любой пары вершин расстояние между ними в подграфе не более чем в t раз больше расстояния между ними в исходном графе; при этом t называется ''коэффициентом растяжения''. Формальное определение остовам дали Пелег и Шеффер [14], хотя связанные с ними понятия неявно использовал Авербух [3] в контексте сетевых синхронизаторов.
[[Остов]] – это ''разреженный'' [[подграф]] данного [[неориентированный граф|неориентированного графа]], сохраняющий приближенные расстояния между каждой парой вершин. Более точно, t-остов графа G = (V, E) представляет собой подграф (V, E<math>_{s}</math>), <math>E_{s} \subseteq E</math>, такой, что для любой пары вершин расстояние между ними в подграфе не более чем в t раз больше расстояния между ними в исходном графе; при этом t называется ''коэффициентом растяжения''. Формальное определение остовам дали Пелег и Шеффер [14], хотя связанные с ними понятия неявно использовал Авербух [3] в контексте сетевых синхронизаторов.


Вычисление t-остова наименьшего размера для заданного графа представляет собой важную комбинаторную задачу с множеством вариантов применения. Однако вычисление t-остова наименьшего размера для графа является NP-полной задачей. Фактически (для значений t > 2) NP-полной [10] является даже задача аппроксимации минимального размера t-остова для графа с коэффициентом O(2<math>^{(1-\mu ) ln n)}</math>)  
Вычисление t-остова наименьшего размера для заданного графа представляет собой важную комбинаторную задачу с множеством вариантов применения. Однако вычисление t-остова наименьшего размера для графа является NP-полной задачей. Фактически (для значений t > 2) NP-полной [10] является даже задача аппроксимации минимального размера t-остова для графа с коэффициентом O(2<math>^{(1-\mu ) ln n)}</math>)  
Строка 85: Строка 85:


== Литература ==
== Литература ==
1. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28,1167-1181 (1999)
1. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28,1167-1181 (1999)
2. Althofer, I., Das, G., Dobkin, D.P.,Joseph, D., Soares J.:On sparse  spanners of weighted graphs. Discret. Comput. Geom. 9, 81-100(1993)
 
3. Awerbuch, B.: Complexity of network synchronization. J. Assoc.
2. Althofer, I., Das, G., Dobkin, D.P.,Joseph, D., Soares J.:On sparse  spanners of weighted graphs. Discret. Comput. Geom. 9, 81-100(1993)
 
3. Awerbuch, B.: Complexity of network synchronization. J. Assoc.
Comput. Mach. 32(4), 804-823 (1985)
Comput. Mach. 32(4), 804-823 (1985)
4. Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and lightweight spanners. Tech. Report CS92-22, Weizmann Institute of Science (1992)
 
5. Awerbuch, B., Berger, B., Cowen, L., Peleg D.: Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28,263-277(1998)
4. Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and lightweight spanners. Tech. Report CS92-22, Weizmann Institute of Science (1992)
6. Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30, 532-563 (2007)
 
7. Baswana, S., Telikepalli, K., Mehlhorn, K., Pettie, S.: New construction of (a, /J)-spanners and purely additive spanners. In: Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 672-681
5. Awerbuch, B., Berger, B., Cowen, L., Peleg D.: Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28,263-277(1998)
8. Bollobas, B., Coppersmith, D., Elkin M.: Sparse distance preserves and additive spanners. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 414-423
 
9. Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. 28,210-236 (1998)
6. Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30, 532-563 (2007)
10. Elkin, M., Peleg, D.: Strong inapproximability of the basic k-spanner problem. In: Proc. of 27th International Colloquim on Automata, Languages and Programming, 2000, pp. 636-648
 
11. Elkin, M., Peleg, D.: (1 + e,/J)-spanner construction for general graphs. SIAM J. Comput. 33,608-631 (2004)
7. Baswana, S., Telikepalli, K., Mehlhorn, K., Pettie, S.: New construction of (a, /J)-spanners and purely additive spanners. In: Proceedings of 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 672-681
12. Erdos, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pp. 29-36. Publ. House Czechoslovak Acad. Sci., Prague (1964)
 
13. Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript (1996)
8. Bollobas, B., Coppersmith, D., Elkin M.: Sparse distance preserves and additive spanners. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 414-423
14. Peleg, D., Schaffer, A.A.: Graph spanners. J. Graph Theory 13, 99-116(1989)
 
15. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740-747 (1989)
9. Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput. 28,210-236 (1998)
16. Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. Assoc. Comput Mach. 36(3), 510-530 (1989)
 
17. Salowe,  J.D.:  Construction  of  multidimensional  spanner graphs, with application to minimum spanning trees. In: ACM Symposium on Computational Geometry, 1991, pp. 256-261
10. Elkin, M., Peleg, D.: Strong inapproximability of the basic k-spanner problem. In: Proc. of 27th International Colloquim on Automata, Languages and Programming, 2000, pp. 636-648
18. Thorup, M., Zwick, U.: Approximate distance oracles. J. Assoc. Comput. Mach. 52,1-24 (2005)
 
19. Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 802-809
11. Elkin, M., Peleg, D.: (1 + e,/J)-spanner construction for general graphs. SIAM J. Comput. 33,608-631 (2004)
 
12. Erdos, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pp. 29-36. Publ. House Czechoslovak Acad. Sci., Prague (1964)
 
13. Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript (1996)
 
14. Peleg, D., Schaffer, A.A.: Graph spanners. J. Graph Theory 13, 99-116(1989)
 
15. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740-747 (1989)
 
16. Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. Assoc. Comput Mach. 36(3), 510-530 (1989)
 
17. Salowe,  J.D.:  Construction  of  multidimensional  spanner graphs, with application to minimum spanning trees. In: ACM Symposium on Computational Geometry, 1991, pp. 256-261
 
18. Thorup, M., Zwick, U.: Approximate distance oracles. J. Assoc. Comput. Mach. 52,1-24 (2005)
 
19. Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 802-809
Источник — http://pco.iis.nsk.su/wega/index.php/Алгоритмы_поиска_остова_во_взвешенном_графе