Проблема дерева Штайнера

• Определение и история дерева Штайнера

  • Дерево Штайнера — это минимальное остовное дерево, которое соединяет все вершины графа. 
  • Задача о дереве Штайнера была сформулирована в 1930-х годах и имеет множество приложений в различных областях. 

• Вариации и обобщения задачи

  • Задача о дереве Штайнера может быть обобщена на евклидовы и прямолинейные деревья Штайнера. 
  • Существуют различные варианты задачи, включая задачи о покрытии и остовном дереве. 

• Алгоритмы решения задачи

  • Алгоритм Коу и соавторов 1976 года является первым алгоритмом, который решает задачу за полиномиальное время. 
  • Алгоритм Ву и соавторов 1986 года улучшает время выполнения, но не улучшает соотношение затрат. 
  • Алгоритмы аппроксимации были разработаны для улучшения соотношения затрат, включая алгоритм Робинса и Зеликовского 2000 года. 

• Параметризованная сложность и аппроксимация

  • Существуют алгоритмы с фиксированными параметрами, но они имеют экспоненциальное пространство. 
  • Существуют полиномиальные алгоритмы с параметризацией по количеству терминалов или ребер, но они не работают в полиномиальное время для всех весов ребер. 
  • Задача допускает приближенную схему ядер полиномиального размера (PSAKS), но не имеет полиномиального ядра. 

• Коэффициент Штайнера

  • Коэффициент Штайнера — это максимальное отношение общей длины минимального остовного дерева к минимальному дереву Штайнера. 
  • Гипотеза о коэффициенте Штайнера остается открытой, но существуют верхние границы для евклидова и прямолинейного дерева Штайнера.