Аноним

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

Материал из WEGA
м
Строка 48: Строка 48:


Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи.
Недавно Чекури и коллеги [7] использовали остовные деревья с низким растяжением для выведения приближенного алгоритма для задачи построения неоднородных сетей с применением «оптового» подхода. Данный алгоритм впервые обеспечивает гарантированную полилогарифмическую аппроксимацию этой задачи.
В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем парам вершин, а не по всем ребрам. Результат находок Абрахама и коллег [ ], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам.
В своей недавней работе Абрахам и коллеги [1] использовали технику звездчатой декомпозиции, предложенную Элкиным и др. [9], для построения вложений с константным средним растяжением, где среднее значение берется по всем ''парам вершин'', а не по всем ребрам. Результат находок Абрахама и коллег [1], в свою очередь, был использован в недавней работе Элкина и др. [10], посвященной фундаментальным контурам.


== Открытые вопросы ==
== Открытые вопросы ==
4551

правка