Полностью динамическая связность высоких степеней: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Строка 70: Строка 70:


3. <math>O(n \alpha (n)) \; </math> на одно обновление или один запрос для k = 4.
3. <math>O(n \alpha (n)) \; </math> на одно обновление или один запрос для k = 4.


== Применение ==
== Применение ==
Строка 76: Строка 77:


== Открытые вопросы ==
== Открытые вопросы ==
Эппстайн и коллеги [], а также Холм и коллеги [12] поднимают интересные вопросы. Во-первых, если эффективные динамические алгоритмы вычисления k-реберной связности для общих значений k известны, то для вычисления k-вершинной связности при k > 5 эффективных полностью динамических алгоритмов еще не создано – более того, нет даже статических.  Во-вторых, полностью динамические задачи 2-реберной и 2-вершинной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы для полностью динамических задач 3-реберной и 3-вершинной связности.
Эппстайн и коллеги [], а также Холм и коллеги [12] поднимают интересные вопросы. Во-первых, если эффективные динамические алгоритмы вычисления k-реберной связности для общих значений k известны, то для вычисления k-вершинной связности при <math>k \ge 5 \; </math> эффективных полностью динамических алгоритмов еще не создано – более того, нет даже статических.  Во-вторых, полностью динамические задачи 2-реберной и 2-вершинной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы для полностью динамических задач 3-реберной и 3-вершинной связности.




Строка 91: Строка 92:
== Литература ==
== Литература ==
1. Dinitz, E.A.: Maintaining the 4-edge-connected components of a graph on-line. In: Proc. 2nd Israel Symp. Theory of Computing and Systems, 1993, pp. 88-99
1. Dinitz, E.A.: Maintaining the 4-edge-connected components of a graph on-line. In: Proc. 2nd Israel Symp. Theory of Computing and Systems, 1993, pp. 88-99
2. Dinitz, E.A., Karzanov A.V., Lomonosov M.V.: On the structure of the system of minimal edge cuts in a graph. In: Fridman, A.A. (ed) Studies in Discrete Optimization, pp. 290-306. Nauka, Moscow (1990). In Russian
2. Dinitz, E.A., Karzanov A.V., Lomonosov M.V.: On the structure of the system of minimal edge cuts in a graph. In: Fridman, A.A. (ed) Studies in Discrete Optimization, pp. 290-306. Nauka, Moscow (1990). In Russian
3. Eppstein, D., Galil Z., Italiano G.F., Nissenzweig A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comput. Mach. 44(5), 669-696 (1997)
3. Eppstein, D., Galil Z., Italiano G.F., Nissenzweig A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comput. Mach. 44(5), 669-696 (1997)
4. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484-538 (1997)
4. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484-538 (1997)
5. Galil, Z., Italiano, G. F.: Fully dynamic algorithms for 2-edge-connectivity. SIAM J. Comput. 21,1047-1069 (1992)
5. Galil, Z., Italiano, G. F.: Fully dynamic algorithms for 2-edge-connectivity. SIAM J. Comput. 21,1047-1069 (1992)
6. Galil, Z., Italiano, G.F.: Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput. 22,11 -28 (1993) Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
7. Henzinger, M.R.: Fully dynamic biconnectivity in graphs. Algorithmica 13(6), 503-538 (1995)
8. Henzinger, M.R.: Improved data structures for fully dynamic biconnectivity. SIAM J. Comput. 29(6), 1761 -1815 (2000)


6. Galil, Z., Italiano, G.F.: Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput. 22,11-28 (1993) Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
7. Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
8. Henzinger, M.R.: Fully dynamic biconnectivity in graphs. Algorithmica 13(6), 503-538 (1995)


9. Henzinger, M.R.: Improved data structures for fully dynamic biconnectivity. SIAM J. Comput. 29(6), 1761–1815 (2000)


10. Henzinger, M., King V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95), 1995, pp. 664-672
10. Henzinger, M., King V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95), 1995, pp. 664-672
11. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)
11. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)
12. Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48,723-760 (2001)
12. Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48,723-760 (2001)
13. Karzanov, A.V., Timofeev, E. A.: Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybernetics 22, 156-162(1986)
13. Karzanov, A.V., Timofeev, E. A.: Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybernetics 22, 156-162(1986)
14. La Poutre, J.A.: Maintenance of triconnected components of graphs. In: Proc. 19th Int. Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 623, pp. 354-365. Springer, Berlin (1992)
14. La Poutre, J.A.: Maintenance of triconnected components of graphs. In: Proc. 19th Int. Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 623, pp. 354-365. Springer, Berlin (1992)
15. La Poutre, J.A.: Maintenance of 2- and 3-edge-connected components of graphs II. SIAM J. Comput. 29(5), 1521 -1549 (2000)
15. La Poutre, J.A.: Maintenance of 2- and 3-edge-connected components of graphs II. SIAM J. Comput. 29(5), 1521 -1549 (2000)
16. La Poutre, J.A., van Leeuwen, J., Overmars, M.H.: Maintenance of 2- and 3-connected components of graphs, part I: 2- and 3-edge-connected components. Discret. Math. 114, 329-359 (1993)
16. La Poutre, J.A., van Leeuwen, J., Overmars, M.H.: Maintenance of 2- and 3-connected components of graphs, part I: 2- and 3-edge-connected components. Discret. Math. 114, 329-359 (1993)
17. La Poutre, J.A., Westbrook, J.: Dynamic two-connectivity with backtracking. In: Proc. 5th ACM-SIAM Symp. Discrete Algorithms, 1994, pp. 204-212
17. La Poutre, J.A., Westbrook, J.: Dynamic two-connectivity with backtracking. In: Proc. 5th ACM-SIAM Symp. Discrete Algorithms, 1994, pp. 204-212
18. Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464 (1992)
18. Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464 (1992)
4551

правка

Навигация