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

Применяя остовные деревья с низким растяжением, предложенные в [9], можно уменьшить время решения таких систем линейных уравнений до <math>m log^{O(1)} n log(1 / \epsilon) \;</math> и до <math>O( n(log \; n \; log \; log \; n ) log (1 / \epsilon)) </math> в случае, если системы планарны. Используя недавно разработанную редукцию Бомана, Хендриксона и Вавасиса [6], можно получить алгоритм решения систем линейных уравнений, возникающих при применении метода конечных элементов для решения двумерных эллиптических уравнений в частных производных, с временем исполнения <math>O(n(log \; n \; log \; log \; n)^2 log(l / \epsilon))</math>.

Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи.