4551
правка
Остовные деревья с низким растяжением: различия между версиями
Материал из WEGA
Остовные деревья с низким растяжением (посмотреть исходный код)
Версия от 12:57, 20 июля 2015
, 20 июля 2015→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 44: | Строка 44: | ||
Применяя остовные деревья с низким растяжением, предложенные в [9], можно уменьшить время решения таких систем линейных уравнений до <math>m log^{O(1)} n log(1 / \epsilon) \;</math> и до O(n(log | Применяя остовные деревья с низким растяжением, предложенные в [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] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи. | ||
В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем парам вершин, а не по всем ребрам. Результат находок Абрахама и коллег [ ], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам. | В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем парам вершин, а не по всем ребрам. Результат находок Абрахама и коллег [ ], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам. | ||
