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

== Применение ==

Некоторые задачи, имеющие отношение к работе Эппстайна и коллег [2, 3], остаются нерешенными. Во-первых, можно ли улучшить время исполнения? Во-вторых, как и в случае графов общего вида, в случае планарных графов полностью динамические задачи 2-реберной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы хотя бы для полностью динамических задач 3-реберной и 3-вершинной связности. В третьих, можно ли в специальном случае планарных графов решить полностью динамическую задачу k-вершинной связности для любого k?

1. Galil Z., Italiano G.F., Sarnak N.: Fully dynamic planarity testing with applications. J. ACM 48, 28-91 (1999)

2. Eppstein D., Galil Z., Italiano G.F., Spencer T.H.: Separator based sparsification I: planarity testing and minimum spanning trees. J. Comput. Syst. Sci., Special issue of STOC 93 52(1), 3-27 (1996)

3. Eppstein D., Galil Z., Italiano G.F., Spencer T.H.: Separator based sparsification II: edge and vertex connectivity. SIAM J. Comput. 28,341-381 (1999)

4. Giammarresi D., Italiano G.F.: Decremental 2- and 3-connectivity on planar graphs. Algorithmica 16(3), 263-287 (1996)

5. Hershberger J., M.R., Suri S.: Data structures for two-edge connectivity in planar graphs. Theor. Comput. Sci. 130(1), 139-161 (1994)