Каков наилучший алгоритм вычисления прямолинейного минимального дерева Штейнера? - PullRequest
Новая
       16

Каков наилучший алгоритм вычисления прямолинейного минимального дерева Штейнера?

2 голосов
/ 24 ноября 2011

Существует много алгоритмов, которые находят аппроксимации прямолинейных деревьев минимума Штейнера (RSMT).Среди них:

  • набор алгоритмов, которые находят минимальные остовные деревья
  • RST-T (прямолинейное одиночное стволовое дерево Штейнера)
  • BGA (жадный алгоритм с пакетной обработкой)
  • BI1S (пакетное итеративное дерево 1-Штейнера)
  • FLUTE (метод быстрого поиска на основе таблицы для построения RSMT и оценки длины провода)

Было показано, что длинаRSMT может быть в 3/2 раза больше, чем у прямоугольного остовного минимального дерева.Я не нашел в литературе границ для других алгоритмов.Они существуют?

FLUTE кажется наиболее эффективным алгоритмом из всех, но я не знаю, наихудший случай и верхняя граница.Был ли он найден?

Имеет ли какой-либо алгоритм ограничение менее 3/2?

1 Ответ

2 голосов
/ 25 ноября 2011

Арора и Митчелл дали схемы аппроксимации за полиномиальное время (= для всех эпсилон> 0, (1 + эпсилон) -приближение) для евклидова дерева Штейнера.Я считаю, что идеи могут быть легко адаптированы к прямолинейному варианту.

...