4431
правка
Остовные деревья с низким растяжением: различия между версиями
Материал из WEGA
Остовные деревья с низким растяжением (посмотреть исходный код)
Версия от 12:58, 20 июля 2015
, 20 июля 2015→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 48: | Строка 48: | ||
Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи. | Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи. | ||
В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем парам вершин, а не по всем ребрам. Результат находок Абрахама и коллег [ ], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам. | В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем ''парам вершин'', а не по всем ребрам. Результат находок Абрахама и коллег [1], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
