Проблема дерева Штейнера или проблема минимального дерева Штейнера , названная в честь Якоба Штайнера , является общим термином для класса задач комбинаторной оптимизации . Хотя проблемы дерева Штейнера могут быть сформулированы в виде множества настроек, все они требуют оптимального межсоединения для данного набора объектов и заранее определенной целевой функции. Одним из хорошо известных вариантов, который часто используется как синоним термина «проблема дерева Штейнера», является проблема дерева Штейнера в графах . Для неориентированного графа с неотрицательными весами ребер и подмножеством вершин, обычно называемых терминалами, проблема дерева Штейнера в графах требует наличиядерево минимального веса, которое содержит все терминалы (но может включать дополнительные вершины). Другими хорошо известными вариантами являются проблема евклидова дерева Штейнера и проблема прямолинейного минимального дерева Штейнера .
Проблема дерева Штейнера на графах можно рассматривать как обобщение двух других известных задач комбинаторной оптимизации: (неотрицательного) кратчайшего пути проблемы и минимального остовного дерева проблемы . Если проблема дерева Штейнера в графах содержит ровно два терминала, она сводится к поиску кратчайшего пути. Если, с другой стороны, все вершины являются терминалами, проблема дерева Штейнера в графах эквивалентна минимальному остовному дереву. Однако, хотя и неотрицательный кратчайший путь, и проблема минимального остовного дерева решаются за полиномиальное время, вариант решения проблемы дерева Штейнера в графах является NP-полным (что означает, что вариант оптимизации является NP-трудным ); Фактически, вариант решения входил в число исходных 21 NP-полных проблем Карпа . Проблема дерева Штейнера в графах имеет приложения в схемотехнике или проектировании сетей . Однако для практических приложений обычно требуются вариации, что порождает множество вариантов задач дерева Штейнера.
Большинство версий проблемы дерева Штейнера NP-трудны , но некоторые ограниченные случаи могут быть решены за полиномиальное время . Несмотря на пессимистическую сложность наихудшего случая, несколько вариантов проблемы дерева Штейнера, включая проблему дерева Штейнера в графах и проблему прямолинейного дерева Штейнера, могут быть эффективно решены на практике даже для крупномасштабных реальных проблем. [1] [2]
Евклидово дерево Штейнера
Первоначальная проблема была сформулирована в форме, которая стала известна как проблема евклидова дерева Штейнера или проблема геометрического дерева Штейнера : для заданных N точек на плоскости цель состоит в том, чтобы соединить их линиями минимальной общей длины таким образом, чтобы любые две точки могут быть соединены отрезками прямых либо напрямую, либо через другие точки и отрезки. Можно показать, что сегменты соединительной линии не пересекаются друг с другом, кроме как в конечных точках, и образуют дерево, отсюда и название проблемы.
Проблема для N = 3 рассматривалась давно и быстро расширилась до задачи поиска звездообразной сети с одним концентратором, соединяющимся со всеми N заданными точками минимальной общей длины. Однако, хотя полная проблема дерева Штейнера была сформулирована в письме Гаусса , ее первое серьезное рассмотрение было в статье 1934 года, написанной на чешском языке Войтехом Ярником и Милошем Кёсслером . Эта статья долгое время игнорировалась, но она уже содержит «практически все общие свойства деревьев Штейнера», позже приписываемые другим исследователям, включая обобщение проблемы с плоскости на более высокие измерения. [3]
Для задачи Евклида Штейнера точки, добавленные к графу ( точки Штейнера ), должны иметь степень три, а три ребра, инцидентные такой точке, должны образовывать три угла в 120 градусов (см. Точку Ферма ). Отсюда следует, что максимальное количество точек Штейнера, которое может иметь дерево Штейнера, равно N - 2, где N - начальное количество данных точек.
Для N = 3 возможны два случая: если треугольник, образованный данными точками, имеет все углы, меньшие 120 градусов, решение дается точкой Штейнера, расположенной в точке Ферма ; в противном случае решение дается двумя сторонами треугольника, которые пересекаются под углом 120 или более градусов.
Для общего N проблема евклидова дерева Штейнера является NP-трудной , и поэтому неизвестно, можно ли найти оптимальное решение с помощью алгоритма с полиномиальным временем . Однако существует схема полиномиального приближения (PTAS) для евклидовых деревьев Штейнера, т. Е. Почти оптимальное решение может быть найдено за полиномиальное время. [4] Неизвестно, является ли проблема евклидова дерева Штейнера NP-полной, поскольку неизвестна принадлежность к классу сложности NP.
Прямолинейное дерево Штейнера
Задача о прямолинейном дереве Штейнера - это вариант геометрической задачи о дереве Штейнера на плоскости, в которой евклидово расстояние заменено на прямолинейное расстояние . Проблема возникает в физической конструкции в электронной автоматизации проектирования . В СБИС , проволока маршрутизации осуществляется с помощью проводов , которые часто ограничены по правилам дизайна , чтобы работать только в вертикальном и горизонтальном направлениях, так что прямолинейные Штайнер дерево проблем может быть использован для моделирования маршрутизации сетей с более чем двумя терминалами. [5]
Дерево Штейнера в графах и вариантах
Деревья Штейнера широко изучались в контексте взвешенных графов . Прототипом, возможно, является проблема дерева Штейнера в графах . Пусть G = ( V , E ) - неориентированный граф с неотрицательными весами ребер c, и пусть S ⊆ V - подмножество вершин, называемых терминалами . Дерево Штейнера является деревом в G , что пролеты S . Есть две версии проблемы: в задаче оптимизации, связанной с деревьями Штейнера, задача состоит в том, чтобы найти дерево Штейнера минимального веса; в задаче решения веса ребер являются целыми числами, и задача состоит в том, чтобы определить, существует ли дерево Штейнера, общий вес которого не превышает заранее заданное натуральное число k . Проблема решения - одна из 21 NP-полных проблем Карпа ; следовательно, проблема оптимизации NP-сложна .
Частный случай этой проблемы - когда G - полный граф , каждая вершина v ∈ V соответствует точке в метрическом пространстве , а веса ребер w ( e ) для каждого e ∈ E соответствуют расстояниям в пространстве. Иначе говоря, веса ребер удовлетворяют неравенству треугольника . Этот вариант известен как проблема метрического дерева Штейнера . Имея пример (неметрической) проблемы дерева Штейнера, мы можем преобразовать его за полиномиальное время в эквивалентный пример метрической проблемы дерева Штейнера; преобразование сохраняет фактор аппроксимации. [6]
Хотя евклидова версия допускает PTAS, известно, что проблема метрического дерева Штейнера является APX-полной , то есть, если P = NP , невозможно достичь коэффициентов аппроксимации, которые сколь угодно близки к 1 за полиномиальное время. Существует алгоритм с полиномиальным временем, который аппроксимирует минимальное дерево Штейнера с точностью до множителя; [7] однако с точностью до множителяNP-сложно. [8] Для ограниченного случая задачи дерева Штейнера с расстояниями 1 и 2 известен алгоритм 1,25-аппроксимации. [9] Карпинский и Александр Зеликовский построили PTAS для плотных экземпляров задач дерева Штейнера. [10]
В особом случае задачи графа, задача дерева Штейнера для квази-двудольный графов , S требуется , чтобы включать , по меньшей мере , один конец каждого ребра в G .
Проблема дерева Штейнера также исследовалась в более высоких измерениях и на различных поверхностях. Были найдены алгоритмы поиска минимального дерева Штейнера на сфере, торе, проективной плоскости , широких и узких конусах и других. [11]
Другие обобщения задачи дерева Штейнера являются к -Станкам соединенной проблема сети Steiner и к -vertex соединенных проблем с сетью Штейнера , где цель состоит в том, чтобы найти K -Станка-связного граф , или к -vertex-связный граф скорее чем любой связный граф.
Проблема Штейнера также была сформулирована в общих условиях метрических пространств и, возможно, для бесконечного числа точек. [12]
Аппроксимация дерева Штейнера
Общая проблема дерева Штейнера графа может быть аппроксимирована путем вычисления минимального остовного дерева подграфа метрического замыкания графа, индуцированного концевыми вершинами, как впервые опубликовано в 1981 году Kou et al. [13] Метрика замыкание графа G полный граф , в котором каждое ребро взвешивается по кратчайшему расстоянию пути между узлами в G . Этот алгоритм создает дерево, вес которого находится в пределах 2 - 2 / t множителя веса оптимального дерева Штейнера, где t - количество листьев в оптимальном дереве Штейнера; это можно доказать, рассмотрев поездку коммивояжера по оптимальному дереву Штейнера. Это приближенное решение вычислимо за полиномиальное время O (| S | | V | ²) , сначала решив задачу кратчайших путей для всех пар для вычисления замыкания метрики, а затем решив задачу минимального остовного дерева .
Другой популярный алгоритм аппроксимации дерева Штейнера в графах был опубликован Такахаши и Мацуямой в 1980 году. [14] Их решение постепенно строит дерево Штейнера, начиная с произвольной вершины и многократно добавляя кратчайший путь от дерева к ближайшей вершине. в S , который еще не добавлен. Этот алгоритм также имеет время работы O (| S | | V | ²) и создает дерево, вес которого находится в пределах 2 - 2 / | S | оптимального.
В 1986 году Wu et al. [15] значительно улучшили время работы, избегая предварительного вычисления кратчайших путей для всех пар. Вместо этого они используют подход, аналогичный алгоритму Краскала для вычисления минимального остовного дерева, начиная с леса | S | непересекающиеся деревья и "выращивание" их одновременно с использованием поиска в ширину, напоминающего алгоритм Дейкстры, но начиная с нескольких начальных вершин. Когда поиск встречает вершину, которая не принадлежит текущему дереву, два дерева объединяются в одно. Этот процесс повторяется до тех пор, пока не останется только одно дерево. Используя кучу (структуру данных) для реализации очереди приоритетов и структуру данных с непересекающимися наборами для отслеживания, к какому дереву принадлежит каждая посещенная вершина, этот алгоритм достигает времени работы O (| E | log | V |), хотя это не так. улучшить соотношение затрат 2–2 / т, предложенное Коу и др.
В серии статей представлены алгоритмы аппроксимации для задачи о минимальном дереве Штейнера с коэффициентами аппроксимации, которые улучшились по сравнению с соотношением 2–2 / t . Эта последовательность завершилась разработкой алгоритма Робинса и Зеликовского в 2000 году, который улучшил коэффициент до 1,55 путем итеративного улучшения остовного дерева терминала с минимальной стоимостью. Однако совсем недавно Ярослав Бырка и др. оказалсяаппроксимация с использованием релаксации линейного программирования и метода, называемого итеративным рандомизированным округлением. [7]
Параметризованная сложность дерева Штейнера
Общая проблема дерева Штейнера графа известна как управляемая с фиксированным параметром , с числом терминалов в качестве параметра, с помощью алгоритма Дрейфуса-Вагнера. [16] [17] Время работы алгоритма Дрейфуса-Вагнера составляет, где - количество вершин графа, а это набор терминалов. Существуют более быстрые алгоритмы, работающие в время для любого или, в случае небольшого веса, время, где - максимальный вес любого ребра. [18] [19] Недостатком вышеупомянутых алгоритмов является то, что они используют экспоненциальное пространство ; существуют алгоритмы полиномиального пространства, работающие в время и время. [20] [21]
Известно, что общая задача графа Штейнера не имеет параметризованного алгоритма, работающего в время для любого , где - количество ребер оптимального дерева Штейнера, если только задача Set cover не имеет алгоритма, работающего в время для некоторых , где а также - количество элементов и количество наборов, соответственно, экземпляра задачи покрытия множеств. [22] Кроме того, известно, что задача не допускает полиномиального ядра, если только, даже параметризованное числом ребер оптимального дерева Штейнера и если все веса ребер равны 1. [23]
Коэффициент Штейнера
Коэффициент Штейнера - это верхняя грань отношения общей длины минимального остовного дерева к минимальному дереву Штейнера для набора точек на евклидовой плоскости. [24]
В проблеме евклидова дерева Штейнера предполагается, что отношение Штейнера равно , отношение, которое достигается тремя точками в равностороннем треугольнике с остовным деревом, использующим две стороны треугольника, и деревом Штейнера, соединяющим точки через центр тяжести треугольника. Несмотря на более ранние утверждения о доказательстве [25], гипотеза все еще остается открытой. [26] Наилучшая широко принятая верхняя оценка задачи - 1,2134, сделанная Чангом и Грэхэмом (1985) .
Для прямолинейной задачи о дереве Штейнера отношение Штейнера в точности равно , соотношение, которое достигается четырьмя точками в квадрате с остовным деревом, использующим три стороны квадрата, и деревом Штейнера, которое соединяет точки через центр квадрата. [27] Точнее, для расстояние, на которое должен быть наклонен квадрат относительно осей координат, а при расстояние квадрат должен быть выровнен по оси.
Смотрите также
- Проблема непрозрачного леса
- Проблема коммивояжера
Заметки
- ^ "Отчет Ползина и Вахдати Данешманд" (PDF) . Проверено 11 ноября +2016 .
- ^ Juhl et al. (2014) .
- ^ Корте, Бернхард ; Нешетржил, Ярослав (2001), «Работа Войтеха Ярника по комбинаторной оптимизации», Дискретная математика , 235 (1–3): 1–17, doi : 10.1016 / S0012-365X (00) 00256-9 , hdl : 10338.dmlcz / 500662 , Руководство по ремонту 1829832.
- ^ Crescenzi et al. (2000) .
- ^ Шервани (1993) , стр. 228.
- ^ Вазирани (2003) , стр. 27-28.
- ^ а б Byrka et al. (2010) .
- ^ Хлебик и Хлебикова (2008) .
- Перейти ↑ Berman, Karpinski & Zelikovsky (2009) .
- ^ Карпинский и Zelikovsky (1998) .
- ^ Смит и Винтер (1995) , стр. 361.
- ^ Паолини и Степанов (2012) .
- ^ Коу, Марковский & Berman (1981) .
- Перейти ↑ Takahashi & Matsuyama (1980) .
- ^ У, Widmayer & Wong (1986) .
- ^ Дрейфус и Вагнер .
- ↑ Левин .
- ^ Fuchs et al .
- ^ Björklund et al .
- ^ Lokshtanov & Nederlof .
- ^ Фомин и др .
- ^ Cygan et al .
- ^ Дом, Lokshtanov & Саурабй .
- ^ Ganley (2004) .
- ↑ The New York Times от 30 октября 1990 года сообщила, что доказательство было найдено, и что Рональд Грэм , предложивший 500 долларов за доказательство, собирался отправить авторам чек по почте.
- ^ Иванов и Тужилин (2012) .
- ^ Хван (1976) .
Рекомендации
- Берман, Петр; Карпинский, Марек ; Зеликовский, Александр (2009). «1.25-аппроксимационный алгоритм для задачи дерева Штейнера с расстояниями 1 и 2». Алгоритмы и структуры данных: 11-й Международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г., Материалы . Конспект лекций по информатике. 5664 . С. 86–97. arXiv : 0810.1851 . DOI : 10.1007 / 978-3-642-03367-4_8 .
- Берн, Маршалл В .; Грэм, Рональд Л. (1989). «Задача кратчайшей сети». Scientific American . 260 (1): 84–89. Bibcode : 1989SciAm.260a..84B . DOI : 10.1038 / Scientificamerican0189-84 .
- Бьёрклунд, Андреас; Хусфельдт, Тор; Каски, Петтери; Койвисто, Микко (2007). «Фурье встречает Мёбиуса: быстрая свертка подмножества». Материалы 39-го симпозиума ACM по теории вычислений . С. 67–74. arXiv : cs / 0611101 . DOI : 10.1145 / 1250790.1250801 .
- Byrka, J .; Грандони, Ф .; Rothvoß, T .; Санита, Л. (2010). «Улучшенное приближение на основе LP для дерева Штейнера». Материалы 42-го симпозиума ACM по теории вычислений . С. 583–592. CiteSeerX 10.1.1.177.3565 . DOI : 10.1145 / 1806689.1806769 .
- Хлебик, Мирослав; Хлебикова, Янка (2008). «Проблема дерева Штейнера на графах: результаты о несовместимости». Теоретическая информатика . 406 (3): 207–214. DOI : 10.1016 / j.tcs.2008.06.046 .
- Чанг, ФРГ ; Грэм, Р.Л. (1985). «Новая оценка евклидовых минимальных деревьев Штейнера». Дискретная геометрия и выпуклость (Нью-Йорк, 1982) . Летопись Нью-Йоркской академии наук. 440 . Нью-Йорк: Нью-Йоркская академия наук. С. 328–346. Bibcode : 1985NYASA.440..328C . DOI : 10.1111 / j.1749-6632.1985.tb14564.x . Руководство по ремонту 0809217 .
- Чеслик, Дитмар (1998). Деревья Штайнера-минимал . п. 319. ISBN 0-7923-4983-0.
- Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпинский, Марек ; Woeginger, Герхард (2000). «Минимальное геометрическое дерево Штейнера» . Сборник задач оптимизации NP .
- Циган, Марек; Делл, Хольгер; Локштанов Даниил; Маркс, Даниэль; Недерлоф, Джеспер; Окамото, Йошио; Патури, Рамамохан; Саураб, Сакет; Вальстрём, Магнус (2016). «О проблемах столь же сложных, как CNF-SAT» . ACM-транзакции по алгоритмам . 12 (3): 41: 1–41: 24. DOI : 10.1145 / 2925416 . S2CID 7320634 .
- Дом, Майкл; Локштанов Даниил; Саураб, Сакет (2014). «Нижние границы ядра с помощью цветов и идентификаторов». ACM-транзакции по алгоритмам . 11 (2): 13: 1–13: 20. DOI : 10.1145 / 2650261 . S2CID 13570734 .
- Дрейфус, ЮВ; Вагнер, Р.А. (1971). «Проблема Штейнера в графах». Сети . 1 (3): 195–207. DOI : 10.1002 / нетто.3230010302 .
- Фомин, Федор В .; Каски, Петтери; Локштанов Даниил; Панолан, Фахад; Саураб, Сакет. "Параметризованный одноэкспоненциальный алгоритм полиномиального пространства времени для дерева Штейнера". Автоматов Языки и программирование - 42 - ая Международная коллоквиум, ICALP 2015, Труды, Часть I . С. 494–505. DOI : 10.1007 / 978-3-662-47672-7_40 .
- Фукс, Бенджамин; Керн, Уолтер; Мёлле, Даниэль; Рихтер, Стефан; Россманиф, Питер; Ван, Синьхуэй (2007). «Динамическое программирование для минимальных деревьев Штейнера» (PDF) . Теория вычислительных систем . 41 (3): 493–500. DOI : 10.1007 / s00224-007-1324-4 . S2CID 7478978 .
- Гэнли, Джозеф Л. (2004). «Коэффициент Штейнера». В черном, Пол Э. (ред.). Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 24 мая 2012 года .
- Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, стр. 208–209, задачи ND12 и ND13.
- Хван, Ф. К. (1976). «О минимальных деревьях Штейнера с прямолинейным расстоянием». Журнал SIAM по прикладной математике . 30 (1): 104–114. DOI : 10.1137 / 0130013 .
- Hwang, FK; Ричардс, Д.С. Уинтер, П. (1992). Проблема дерева Штейнера . Анналы дискретной математики. 53 . Северная Голландия : Эльзевир . ISBN 0-444-89098-X.
- Иванов, Александр; Тужилин, Алексей (1994). Минимальные сети: проблема Штейнера и ее обобщения . Северо-Запад, Бока-Ратон, Флорида: CRC Press . ISBN 978-0-8493-8642-8.
- Иванов, Александр; Тужилин, Алексей (2000). Ветвящиеся решения одномерных вариационных задач . Сингапур-Нью-Джерси-Лондон-Гонконг: World Scientific . ISBN 978-981-02-4060-8.
- Иванов, Александр; Тужилин, Алексей (2003). Теория экстремальных сетей . Москва-Ижевск: Институт компьютерных исследований. ISBN 5-93972-292-X.
- Иванов, Александр; Тужилин, Алексей (2012). «Гипотеза отношения Штейнера Гилберта-Поллака все еще открыта: уточняющее заявление». Алгоритмика . 62 (1–2): 630–632. DOI : 10.1007 / s00453-011-9508-3 . S2CID 7486839 .
- Иванов, Александр; Тужилин, Алексей (2015). «Разветвленные покрытия и коэффициент Штейнера». Международные транзакции в операционных исследованиях (ITOR) . 23 (5): 875–882. arXiv : 1412,5433 . DOI : 10.1111 / itor.12182 . S2CID 3386263 .
- Juhl, D .; Warme, DM; Winter, P .; Захариасен, М. (2014). «Программный пакет GeoSteiner для вычисления деревьев Штейнера на плоскости: обновленное вычислительное исследование». Труды 11-го конкурса внедрения DIMACS (PDF) .
- Карпинский, Марек; Зеликовский, Александр (1998). «Аппроксимация плотных случаев покрывающих задач» . Труды семинара DIMACS по проектированию сетей: возможность подключения и расположение объектов . Серия DIMACS по дискретной математике и теоретической информатике. 40 . Американское математическое общество. С. 169–178.
- Корте, Бернхард ; Выген, Йенс (2006). «Раздел 20.1». Комбинаторная оптимизация: теория и алгоритмы (3-е изд.). Springer . ISBN 3-540-25684-9.
- Kou, L .; Марковский, Г .; Берман, Л. (1 июня 1981 г.). «Быстрый алгоритм для деревьев Штейнера». Acta Informatica . 15 (2): 141–145. DOI : 10.1007 / BF00288961 . S2CID 21057232 .
- Левин, А.Ю. (1971). «Алгоритм кратчайшего соединения группы вершин графа». Советские математические доклады . 12 : 1477–1481.
- Локштанов Даниил; Недерлоф, Джеспер (2010). «Экономия места за счет алгебраизации». Материалы 42-го симпозиума ACM по теории вычислений . С. 321–330. DOI : 10.1145 / 1806689.1806735 .
- Paolini, E .; Степанов, Е. (2012). "Существование и регулярность результатов для проблемы Штейнера" (PDF) . Расчет. Вар. Частичная разница. Уравнения . 46 (3–4): 837–860. DOI : 10.1007 / s00526-012-0505-4 . ЛВП : 2158/600141 . S2CID 55793499 .
- Робинс, Габриэль; Зеликовский, Александр (2000). «Улучшенное приближение дерева Штейнера в графах» . Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '00) . Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. С. 770–779 . ISBN 0-89871-453-2.
- Шервани, Навид А. (1993). Алгоритмы автоматизации физического проектирования СБИС . Kluwer Academic Publishers. ISBN 9781475722192.
- Смит, JM; Уинтер, П. (1995). «Вычислительная геометрия и топологическое проектирование сетей». Ин Ду, Дин-Чжу; Хван, Фрэнк (ред.). Вычисления в евклидовой геометрии . Серия конспектов лекций по вычислительной технике. 4 (2-е изд.). Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., стр. 351–451. ISBN 981-02-1876-1.
- Такахаши, Хиромицу; Мацуяма, Акира (1980). «Приближенное решение проблемы Штейнера в графах». Математика. Japonica . 24 (6): 573–577.
- Вазирани, Виджай В. (2003). Аппроксимационные алгоритмы . Берлин: Springer. ISBN 3-540-65367-8.
- Ву, Банг Е; Чао, Кунь-Мао (2004). «Глава 7». Связующие деревья и проблемы оптимизации . Чепмен и Холл / CRC. ISBN 1-58488-436-3.
- Wu, YF; Widmayer, P .; Вонг, СК (май 1986 г.). «Более быстрый алгоритм приближения для задачи Штейнера в графах». Acta Informatica . 23 (2): 223–229. DOI : 10.1007 / bf00289500 . S2CID 7772232 .
Внешние ссылки
- Hazewinkel, M. (2001) [1994], "Проблема дерева Штейнера" , Энциклопедия математики , EMS Press
- М. Хауптманн, М. Карпинский (2013): Сборник проблем дерева Штейнера
- GeoSteiner ( решатель евклидова и прямолинейного дерева Штейнера; доступен исходный код для некоммерческого использования)
- SCIP-Jack (Решатель для проблемы дерева Штайнера в графах и 11 вариантов; доступен исходный код, бесплатно для академического использования)
- https://archive.org/details/RonaldLG1988 (фильм: Рональд Л. Грэм: Кратчайшая сетевая проблема (1988)
- Подпрограмма Fortran для нахождения вершины Штейнера треугольника (то есть точки Ферма ), ее расстояний от вершин треугольника и относительных весов вершин.
- Филомурка ( Решатель мелкомасштабных задач дерева Штейнера в графах)
- https://www.youtube.com/watch?v=PI6rAOWu-Og (Фильм: решение проблемы дерева Штейнера водой и мылом)
- Ноормохаммадпур, Мохаммад; Raghavendra, Cauligi S .; Рао, Шрирам; Kandula, Srikanth (2017), «Использование деревьев Штейнера для минимизации среднего времени завершения массовых передач данных», DCCast: эффективная передача данных от одной точки к другой между центрами обработки данных , Ассоциация USENIX, arXiv : 1707.02096