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

Компромиссы при решении динамических графовых задач (посмотреть исходный код)

21 байт убрано , 19 июня 2018

4430

правок

@@ Строка 130: / Строка 130: @@
 | <math>O(n^{1,575}) \;</math>
 | <math>O(n^{0,575}) \;</math>
-|
+| Деметреску, Итальяно [4]
 |-
 | Граф общего вида
 | Монте-Карло
 | <math>O(n^{1,575}) \;</math>
-|
+| <math>O(n^{0,575}) \;</math>
-|
+| Санковски [13]
 |-
 | Граф общего вида
 | Монте-Карло
-| <math>O(n^{0,575}) \;</math>
+| <math>O(n^{1,495}) \;</math>
-|
+| <math>O(n^{1,495}) \;</math>
-|
+| Санковски [13]
 |-
 | Граф общего вида
 | Детерминированный
-| <math>O(n^{1,495}) \;</math>
+| <math>O(m \sqrt{n})</math> аморт.
-| <math>O(n^{1,495}) \;</math>
+| <math>O(\sqrt{n)}</math>
-|
+| Родитти, Цвик [10]
 |-
 | Граф общего вида
 | Детерминированный
-|
+| O(m + n log n) аморт.
-|
+| O(n)
-|
+| Родитти, Цвик [11]
 |}
-	O(n0,575)	Деметреску, Итальяно [4]
-O(n1,575)	O(n0,575)	Санковски [13]
-O(n1,495)	O(n1,495)	Санковски [13]
-O(mn) аморт.	O(pn)	Родитти, Цвик [10]
-O(m + n log n) аморт.	O(n)	Родитти, Цвик [11]
 Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения