Оглавление
Проблема дерева Штайнера
-
Определение и история дерева Штайнера
- Дерево Штайнера – это минимальное остовное дерево, которое соединяет все вершины графа.
- Задача о дереве Штайнера была сформулирована в 1930-х годах и имеет множество приложений в различных областях.
-
Вариации и обобщения задачи
- Задача о дереве Штайнера может быть обобщена на евклидовы и прямолинейные деревья Штайнера.
- Существуют различные варианты задачи, включая задачи о покрытии и остовном дереве.
-
Алгоритмы решения задачи
- Алгоритм Коу и соавторов 1976 года является первым алгоритмом, который решает задачу за полиномиальное время.
- Алгоритм Ву и соавторов 1986 года улучшает время выполнения, но не улучшает соотношение затрат.
- Алгоритмы аппроксимации были разработаны для улучшения соотношения затрат, включая алгоритм Робинса и Зеликовского 2000 года.
-
Параметризованная сложность и аппроксимация
- Существуют алгоритмы с фиксированными параметрами, но они имеют экспоненциальное пространство.
- Существуют полиномиальные алгоритмы с параметризацией по количеству терминалов или ребер, но они не работают в полиномиальное время для всех весов ребер.
- Задача допускает приближенную схему ядер полиномиального размера (PSAKS), но не имеет полиномиального ядра.
-
Коэффициент Штайнера
- Коэффициент Штайнера – это максимальное отношение общей длины минимального остовного дерева к минимальному дереву Штайнера.
- Гипотеза о коэффициенте Штайнера остается открытой, но существуют верхние границы для евклидова и прямолинейного дерева Штайнера.
Полный текст статьи: