Остовные деревья с низким растяжением: различия между версиями

Остовные деревья с низким растяжением (посмотреть исходный код)

60 байт добавлено , 20 июля 2015

м

4551

правка

@@ Строка 34: / Строка 34: @@
 == Основные результаты ==
 Эта задача изучалась еще в шестидесятых [8, 13, 15, 16]. Серьезный прогресс был достигнут Алоном и коллегами [2], показавшими, что
-J2(log n) = avestr(n) = expstr(n)
-= exp(O(plog n ■ log log n)) :
-Элкин и коллеги [9] улучшили верхнюю границу и показали, что avestr(n) = expstr(n) = O(log2 n • loglog n) :
+<math>\Omega(log \; n) = avestr(n) = expstr(n) = exp(O( \sqrt{log \; n \cdot log \; log \; n)}).</math>
+Элкин и коллеги [9] улучшили верхнюю границу и показали, что <math>avestr(n) = expstr(n) = O(log^2 n \cdot log \; log \; n).</math>
 == Применение ==