4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 40: | Строка 40: | ||
== Применение == | == Применение == | ||
Применение динамических алгоритмов реберной и вершинной связности приведено в соответствующем разделе статьи | Применение динамических алгоритмов реберной и вершинной связности приведено в соответствующем разделе статьи «[[Полностью динамическая связность высоких степеней]]». Случай планарных графов особенно важен, поскольку они часто встречаются в различных приложениях. | ||
Открытые вопросы | |||
== Открытые вопросы == | |||
Некоторые задачи, имеющие отношение к работе Эппстайна и коллег [2, 3], остаются нерешенными. Во-первых, можно ли улучшить время исполнения? Во-вторых, как и в случае графов общего вида, в случае планарных графов полностью динамические задачи 2-реберной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы хотя бы для полностью динамических задач 3-реберной и 3-вершинной связности. В третьих, можно ли в специальном случае планарных графов решить полностью динамическую задачу k-вершинной связности для любого k? | Некоторые задачи, имеющие отношение к работе Эппстайна и коллег [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) | 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) | 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) | 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) | 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) | 5. Hershberger J., M.R., Suri S.: Data structures for two-edge connectivity in planar graphs. Theor. Comput. Sci. 130(1), 139-161 (1994) |
правок