Задача о дереве Штейнера

Дерево Штейнера для трех точек A , B и C нет прямых связей (обратите внимание, что между A , B , C ). Точка Штейнера S расположена в Ферма треугольника ABC . точке

Решение для четырех точек — есть две точки Штейнера, S ₁ и S _2.

В комбинаторной математике проблема дерева Штейнера или проблема минимального дерева Штейнера , названная в честь Якоба Штайнера , является общим термином для класса задач комбинаторной оптимизации . Хотя задачи дерева Штейнера могут быть сформулированы в различных ситуациях, все они требуют оптимального взаимодействия для данного набора объектов и заранее определенной целевой функции . Одним из хорошо известных вариантов, который часто используется как синоним термина «проблема дерева Штейнера», является проблема дерева Штейнера в графах . Учитывая неориентированный граф с неотрицательными весами ребер и подмножеством вершин, обычно называемых терминалами, задача дерева Штейнера в графах требует дерева минимального веса, которое содержит все терминалы (но может включать дополнительные вершины) и минимизирует общий вес. его краев. Другими хорошо известными вариантами являются задача евклидова дерева Штейнера и задача о прямолинейном минимальном дереве Штейнера .

Задачу о дереве Штейнера в графах можно рассматривать как обобщение двух других известных задач комбинаторной оптимизации: задачи (неотрицательного) кратчайшего пути и задачи минимального остовного дерева . Если задача о дереве Штейнера в графах содержит ровно два терминала, она сводится к поиску кратчайшего пути. Если, с другой стороны, все вершины являются терминалами, проблема дерева Штейнера в графах эквивалентна минимальному остовному дереву. Однако, хотя и неотрицательный кратчайший путь, и проблема минимального остовного дерева разрешимы за полиномиальное время , для задачи дерева Штейнера такое решение не известно. Его вариант решения , запрашивающий, имеет ли данный ввод дерево с весом меньше некоторого заданного порога, является NP-полным , что означает, что вариант оптимизации, запрашивающий дерево с минимальным весом в данном графе, является NP-сложным . Фактически, этот вариант решения был среди первоначальных 21 NP-полной задачи Карпа . Проблема дерева Штейнера в графах имеет применение при компоновке схем или сетевой дизайн . Однако практические приложения обычно требуют вариаций, что приводит к появлению множества вариантов задачи дерева Штейнера.

Большинство версий проблемы дерева Штейнера NP-трудны, но некоторые ограниченные случаи можно решить за полиномиальное время. Несмотря на пессимистическую сложность наихудшего случая , несколько вариантов задачи о дереве Штейнера, включая задачу о дереве Штейнера в графах и задачу о прямолинейном дереве Штейнера, можно эффективно решить на практике даже для крупномасштабных реальных задач.

Евклидово дерево Штейнера

Минимальные деревья Штейнера вершин правильных многоугольников с N = от 3 до 8 сторон. Наименьшая длина сети L для N > 5 равна длине окружности за вычетом одной стороны. Квадраты представляют точки Штейнера.

Исходная задача была сформулирована в форме, которая стала известна как проблема евклидова дерева Штейнера или геометрическая проблема дерева Штейнера : для заданных N точек на плоскости цель состоит в том, чтобы соединить их линиями минимальной общей длины таким образом, чтобы любые две точки могут быть соединены между собой отрезками линий напрямую или через другие точки и отрезки линий.

Хотя проблема названа в честь Штайнера, впервые она была поставлена ​​в 1811 году Жозефом Диесом Жергонном в следующей форме: «Несколько городов расположены в известных местах на плоскости; задача состоит в том, чтобы соединить их вместе системой каналов. общая длина которого как можно меньше».

Можно показать, что соединяющие отрезки прямых не пересекаются друг с другом, кроме как в конечных точках, и образуют дерево, отсюда и название задачи.

Проблема для N = 3 уже давно рассматривалась и быстро расширилась до проблемы поиска звездообразной сети с одним концентратором, соединяющимся со всеми N заданными точками минимальной общей длины.Однако, хотя полная проблема дерева Штейнера была сформулирована в письме Гаусса , ее первое серьезное рассмотрение было в статье 1934 года, написанной на чешском языке Войтехом Ярником и Милошем Кесслером . На эту статью долгое время не обращали внимания, но она уже содержит «практически все общие свойства деревьев Штейнера», позже приписываемые другим исследователям, включая обобщение проблемы с плоскости на более высокие измерения.

Для евклидовой задачи Штейнера добавленные в граф точки ( точки Штейнера ) должны иметь степень три, а три ребра, инцидентные такой точке, должны образовывать три угла по 120 градусов (см. Точка Ферма ). Отсюда следует, что максимальное количество точек Штейнера, которое может иметь дерево Штейнера, равно N − 2 , где N — начальное количество заданных точек. (все эти свойства были установлены еще Жергонном.)

При N = 3 возможны два случая: если треугольник, образованный данными точками, имеет все углы меньше 120 градусов, то решение дается точкой Штейнера, расположенной в точке Ферма ; в противном случае решение дается двумя сторонами треугольника, которые пересекаются под углом 120 или более градусов.

Для общего N задача евклидова дерева Штейнера является NP-трудной , и, следовательно, неизвестно, оптимальное решение можно ли найти с помощью алгоритма с полиномиальным временем . существует схема аппроксимации за полиномиальное время Однако для евклидовых деревьев Штейнера (PTAS), т. е. почти оптимальное решение может быть найдено за полиномиальное время. Неизвестно, является ли задача евклидова дерева Штейнера NP-полной, поскольку неизвестна принадлежность к классу сложности NP.

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

Основная статья: Прямолинейное дерево Штейнера

Задача о прямолинейном дереве Штейнера — это вариант геометрической задачи о дереве Штейнера на плоскости, в которой евклидово расстояние заменено прямолинейным расстоянием . Проблема возникает при физическом проектировании средств автоматизации электронного проектирования . В схемах СБИС прокладка проводов осуществляется с помощью проводов, которые по правилам проектирования часто ограничены прокладкой только в вертикальном и горизонтальном направлениях, поэтому задачу прямолинейного дерева Штейнера можно использовать для моделирования прокладки цепей с более чем двумя терминалами.

Дерево Штейнера в графах и вариантах

Деревья Штейнера широко изучались в контексте взвешенных графов . Прототипом, возможно, является задача о дереве Штейнера в графах . Пусть G = ( V , E ) — неориентированный граф с неотрицательными весами ребер c, и пусть S ⊆ V — подмножество вершин, называемых терминалами . Дерево Штейнера — это дерево в G охватывающее S. , Существует два варианта задачи: в задаче оптимизации, связанной с деревьями Штейнера, задача состоит в нахождении дерева Штейнера с минимальным весом; в задаче принятия решения веса ребер являются целыми числами, и задача состоит в том, чтобы определить, существует ли дерево Штейнера, общий вес которого не превышает заранее определенное натуральное число k . Проблема решения — одна из 21 NP-полной задачи Карпа ; следовательно, задача оптимизации является NP-трудной . Проблемы дерева Штейнера в графах применяются к различным проблемам в исследованиях и промышленности. включая многоадресную маршрутизацию и биоинформатика.

Особым случаем этой проблемы является случай, когда G — полный граф , каждая вершина v ∈ V соответствует точке в метрическом пространстве , а веса ребер w ( e ) для каждого e ∈ E соответствуют расстояниям в пространстве. Другими словами, веса ребер удовлетворяют неравенству треугольника . Этот вариант известен как метрическая проблема дерева Штейнера . Учитывая экземпляр (неметрической) проблемы дерева Штейнера, мы можем за полиномиальное время преобразовать его в эквивалентный экземпляр метрической проблемы дерева Штейнера; преобразование сохраняет коэффициент аппроксимации.

Хотя евклидова версия допускает PTAS, известно, что метрическая задача дерева Штейнера является APX-полной , т. е., если только P = NP , невозможно достичь коэффициентов аппроксимации, сколь угодно близких к 1 за полиномиальное время. Существует алгоритм с полиномиальным временем, который аппроксимирует минимальное дерево Штейнера с точностью до фактора. $\ln(4)+\varepsilon \approx 1.386$; однако аппроксимация с точностью до множителя $96/95\approx 1.0105$ является NP-трудным. Для ограниченного случая задачи Дерева Штейнера с расстояниями 1 и 2 известен алгоритм аппроксимации 1,25. Карпинский и Александр Зеликовский построили PTAS для плотных случаев задач дерева Штейнера.

В частном случае задачи о графах, задаче о дереве Штейнера для квазидвудольных графов , в требуется, чтобы S включал хотя бы одну конечную точку каждого G. ребра

Проблема дерева Штейнера также исследовалась в более высоких измерениях и на различных поверхностях. Алгоритмы поиска минимального дерева Штейнера были найдены на сфере, торе, проективной плоскости , широких и узких конусах и других.

Другими обобщениями проблемы дерева Штейнера являются задача сети Штейнера с k -связными ребрами и задача сети Штейнера с k -связными вершинами , где цель состоит в том, чтобы найти граф с k -связными ребрами или граф с k -связными вершинами , а не чем любой связный граф. Еще один хорошо изученный Обобщением является проблема проектирования живучей сети (SNDP), где задача состоит в том, чтобы соединить каждую пару вершин с заданным количеством (возможно, 0) путей, не пересекающихся по ребрам или вершинам.

Проблема Штейнера также была сформулирована в общей ситуации метрических пространств и, возможно, для бесконечного числа точек.

Аппроксимация дерева Штейнера

Общая проблема дерева Штейнера в графе может быть аппроксимирована путем вычисления минимального остовного дерева подграфа метрического замыкания графа, индуцированного терминальными вершинами, как впервые опубликовано в 1981 году Коу и др. Метрическое замыкание графа G в котором каждое ребро имеет вес по кратчайшему пути между узлами в G. — это полный граф , Этот алгоритм создает дерево, вес которого находится в пределах 2 - 2/ t коэффициента веса оптимального дерева Штейнера, где t - количество листьев в оптимальном дереве Штейнера; это можно доказать, рассмотрев тур коммивояжера по оптимальному дереву Штейнера. Это приближенное решение вычислимо за полиномиальное время O(|S| |V|²) путем сначала решения задачи о кратчайших путях для всех пар для вычисления замыкания метрики, а затем путем решения задачи о минимальном остовном дереве .

Другой популярный алгоритм аппроксимации дерева Штейнера графами был опубликован Такахаши и Мацуямой в 1980 году. Их решение постепенно строит дерево Штейнера, начиная с произвольной вершины и неоднократно добавляя кратчайший путь от дерева к ближайшей вершине в S , которая еще не была добавлена. Этот алгоритм также имеет время работы O(| S | | V |²) и создает дерево, вес которого находится в пределах 2 − 2/| С | оптимального.

В 1986 году Ву и др. значительно улучшилось время работы за счет исключения предварительного вычисления кратчайших путей для всех пар. Вместо этого они используют подход, аналогичный алгоритму Краскала для вычисления минимального остовного дерева, начиная с леса | С | непересекающиеся деревья и «выращивание» их одновременно с использованием поиска в ширину, напоминающего алгоритм Дейкстры , но начиная с нескольких начальных вершин. Когда при поиске встречается вершина, не принадлежащая текущему дереву, два дерева объединяются в одно. Этот процесс повторяется до тех пор, пока не останется только одно дерево. Используя кучу (структуру данных) для реализации очереди приоритетов и структуру данных с непересекающимся набором для отслеживания того, какому дереву принадлежит каждая посещенная вершина, этот алгоритм достигает времени работы O(| E | log | V |), хотя это и не так. улучшить соотношение затрат 2 - 2/ t по данным Kou et al.

В серии статей были представлены алгоритмы аппроксимации для задачи о минимальном дереве Штейнера с коэффициентами аппроксимации, которые улучшаются по сравнению с соотношением 2 - 2/ t . Кульминацией этой последовательности стал алгоритм Робинса и Зеликовского в 2000 году, который улучшил соотношение до 1,55 за счет итеративного улучшения конечного связующего дерева с минимальной стоимостью. Однако совсем недавно Byrka et al. оказался $\ln(4)+\varepsilon \leq 1.39$ аппроксимация с использованием релаксации линейного программирования и метода, называемого итеративным рандомизированным округлением.

Параметризованная сложность дерева Штейнера

Общая задача дерева Штейнера на графе, как известно, решается с помощью алгоритма Дрейфуса-Вагнера с фиксированным параметром и количеством терминалов в качестве параметра. Время работы алгоритма Дрейфуса-Вагнера составляет $3^{|S|}{\text{poly}}(n)$, где n — количество вершин графа, а S — множество терминалов. Существуют более быстрые алгоритмы, работающие в $c^{|S|}{\text{poly}}(n)$ время для любого $c>2$ или, в случае малых весов, $2^{|S|}{\text{poly}}(n)W$ время, где W — максимальный вес любого ребра. Недостатком вышеупомянутых алгоритмов является то, что они используют экспоненциальное пространство ; существуют алгоритмы полиномиального пространства, работающие в $2^{|S|}{\text{poly}}(n)W$ время и $(7.97)^{|S|}{\text{poly}}(n)\log W$ время.

Известно, что общая задача дерева Штейнера на графе не имеет параметризованного алгоритма, работающего в $2^{\epsilon t}{\text{poly}}(n)$ время для любого $\epsilon <1$, где t — количество ребер оптимального дерева Штейнера, если только задача Set Cover не имеет алгоритма, работающего в $2^{\epsilon n}{\text{poly}}(m)$ время для некоторых $\epsilon <1$, где n и m — количество элементов и количество множеств соответственно экземпляра задачи о покрытии множества. Кроме того, известно, что задача не допускает полиномиального ядра, если только ${\textsf {coNP}}\subseteq {\textsf {NP/poly}}$, даже параметризованный количеством ребер оптимального дерева Штейнера и если все веса ребер равны 1.

Параметризованная аппроксимация дерева Штейнера

Хотя задача дерева Штейнера на графе не допускает полиномиального ядра, если только ${\textsf {coNP}}\subseteq {\textsf {NP/poly}}$ параметризованный количеством терминалов, он допускает приближенную схему кернеризации полиномиального размера (PSAKS): для любого $\varepsilon >0$ можно вычислить ядро ​​полиномиального размера, которое теряет только $1+\varepsilon$ фактор качества решения.

При параметризации задачи дерева Штейнера графа числом p нетерминалов (вершин Штейнера) в оптимальном решении задача является W[1]-трудной (в отличие от параметризации числом терминалов, как упоминалось выше). В то же время задача является APX-полной и, следовательно, не допускает PTAS , если только P = NP . Однако существует параметризованная схема аппроксимации , которая для любого $\varepsilon >0$ вычисляет $(1+\varepsilon )$-аппроксимация в $2^{O(p^{2}/\varepsilon ^{4})}n^{O(1)}$ время. Для этой параметризации также существует PSAKS.

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

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

Предполагается, что в задаче о евклидовом дереве Штейнера отношение Штейнера равно ${\tfrac {2}{\sqrt {3}}}\approx 1.1547$, соотношение, которое достигается тремя точками в равностороннем треугольнике с остовным деревом, использующим две стороны треугольника, и деревом Штейнера, соединяющим точки через центр тяжести треугольника. Несмотря на более ранние заявления о доказательствах, гипотеза все еще остается открытой. Наилучшая общепризнанная верхняя граница задачи — 1,2134, предложенная Чангом и Грэмом (1985) .

Для прямолинейной задачи о дереве Штейнера коэффициент Штейнера точно равен ${\tfrac {3}{2}}$, соотношение, которое достигается четырьмя точками в квадрате с остовным деревом, использующим три стороны квадрата, и деревом Штейнера, соединяющим точки через центр квадрата. Точнее, для $L_{1}$ расстояние, на которое должен быть наклонен квадрат $45^{\circ }$ относительно осей координат, а для $L_{\infty }$ расстояние, на котором квадрат должен быть выровнен по оси.

См. также

• Проблема непрозрачного леса
• Задача коммивояжера

Ссылки

• Берман, Петр; Карпински, Марек ; Зеликовский, Александр (2009). «Алгоритм 1,25-аппроксимации задачи дерева Штейнера с расстояниями 1 и 2». Алгоритмы и структуры данных: 11-й Международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г., Материалы . Конспекты лекций по информатике. Том. 5664. стр. 86–97. arXiv : 0810.1851 . дои : 10.1007/978-3-642-03367-4_8 .
• Берн, Маршалл В.; Грэм, Рональд Л. (1989). «Задача о кратчайшей сети». Научный американец . 260 (1): 84–89. Бибкод : 1989SciAm.260a..84B . doi : 10.1038/scientificamerican0189-84 .
• Бьёрклунд, Андреас; Хусфельдт, Тор; Каски, Петтери; Койвисто, Микко (2007). «Фурье встречает Мёбиуса: быстрая свертка подмножества». Материалы 39-го симпозиума ACM по теории вычислений . стр. 67–74. arXiv : cs/0611101 . дои : 10.1145/1250790.1250801 .
• Бирка, Дж.; Грандони, Ф.; Ротвосс, Т.; Санита, Л. (2010). «Улучшенная аппроксимация дерева Штейнера на основе ЛП». Материалы 42-го симпозиума ACM по теории вычислений . стр. 583–592. CiteSeerX   10.1.1.177.3565 . дои : 10.1145/1806689.1806769 .
• Хлебик, Мирослав; Хлебикова, Янка (2008). «Проблема дерева Штейнера на графах: результаты о неаппроксимируемости» . Теоретическая информатика . 406 (3): 207–214. дои : 10.1016/j.tcs.2008.06.046 .
• Чанг, Франция ; Грэм, Р.Л. (1985). «Новая граница для евклидовых минимальных деревьев Штейнера». Дискретная геометрия и выпуклость (Нью-Йорк, 1982) . Анналы Нью-Йоркской академии наук. Том. 440. Нью-Йорк: Нью-Йоркская академия наук. стр. 328–346. Бибкод : 1985NYASA.440..328C . дои : 10.1111/j.1749-6632.1985.tb14564.x . МР   0809217 .
• Чеслик, Дитмар (1998). Минимальные деревья Штейнера . Спрингер. п. 319. ИСБН  0-7923-4983-0 .
• Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Вегингер, Герхард (2000). «Минимальное геометрическое дерево Штейнера» . Сборник задач оптимизации NP .
• Гиган, Марек; Делл, Хольгер; Локштанов Даниил; Маркс, Дэниел; Недерлоф, Йеспер; Окамото, Ёсио; Патури, Рамамохан; Саураб, Сакет; Вальстрем, Магнус (2016). «О таких сложных проблемах, как CNF-SAT» . Транзакции ACM на алгоритмах . 12 (3): 41:1–41:24. arXiv : 1112.2275 . дои : 10.1145/2925416 . S2CID   7320634 .
• Дом, Майкл; Локштанов Даниил; Саураб, Сакет (2014). «Нижние границы кернелизации через цвета и идентификаторы». Транзакции ACM на алгоритмах . 11 (2): 13:1–13:20. дои : 10.1145/2650261 . S2CID   13570734 .
• Дрейфус, SE; Вагнер, Р.А. (1971). «Задача Штейнера в графах». Сети . 1 (3): 195–207. дои : 10.1002/net.3230010302 .
• Фомин Федор Владимирович; Каски, Петтери; Локштанов Даниил; Панолан, Фахад; Саураб, Сакет (2015). «Параметризованный одноэкспоненциальный полиномиальный пространственный алгоритм для дерева Штейнера». Автоматы, языки и программирование – 42-й международный коллоквиум, ICALP 2015, материалы, часть I. стр. 494–505. дои : 10.1007/978-3-662-47672-7_40 . HDL : 1956/23311 .
• Фокс, Бенджамин; Керн, Уолтер; Мёлле, Даниэль; Рихтер, Стефан; Россманит, Питер; Ван, Синьхуэй (2007). «Динамическое программирование для минимальных деревьев Штейнера» (PDF) . Теория вычислительных систем . 41 (3): 493–500. дои : 10.1007/s00224-007-1324-4 . S2CID   7478978 .
• Гэнли, Джозеф Л. (2004). «Коэффициент Штейнера». В черном, Пол Э. (ред.). Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США . Проверено 24 мая 2012 г.
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN  9780716710455 . МР   0519066 . OCLC   247570676 . , стр. 208–209, задачи ND12 и ND13.
• Хван, ФК (1976). «О минимальных деревьях Штейнера с прямолинейным расстоянием». SIAM Journal по прикладной математике . 30 (1): 104–114. дои : 10.1137/0130013 .
• Хван, ФК; Ричардс, Д.С.; Зима, П. (1992). Задача о дереве Штейнера . Анналы дискретной математики. Том. 53. Северная Голландия : Эльзевир . ISBN  0-444-89098-Х .
• Иванов, Александр; Тужилин, Алексей (1994). Минимальные сети: проблема Штейнера и ее обобщения . Северо-запад, Бока-Ратон, Флорида: CRC Press . ISBN  978-0-8493-8642-8 .
• Иванов, Александр; Тужилин, Алексей (2000). Ветвящиеся решения одномерных вариационных задач . Сингапур-Нью-Джерси-Лондон-Гонконг: World Scientific . ISBN  978-981-02-4060-8 .
• Иванов, Александр; Тужилин, Алексей (2003). Теория экстремальных сетей . Москва-Ижевск: Институт компьютерных исследований. ISBN  5-93972-292-Х .
• Иванов, Александр; Тужилин, Алексей (2012). «Гипотеза Гилберта – Поллака об отношении Штейнера все еще остается открытой: уточняющее заявление». Алгоритмика . 62 (1–2): 630–632. дои : 10.1007/s00453-011-9508-3 . S2CID   7486839 .
• Иванов, Александр; Тужилин, Алексей (2015). «Разветвленные накрытия и соотношение Штейнера». Международные сделки в области операционных исследований . 23 (5): 875–882. arXiv : 1412.5433 . дои : 10.1111/itor.12182 . S2CID   3386263 .
• Юл, Д.; Варм, ДМ; Зима, П.; Захариасен, М. (январь 2018 г.). «Пакет программного обеспечения GeoSteiner для расчета деревьев Штейнера на плоскости: обновленное вычислительное исследование» . Математическое программирование вычислений . 10 (4): 487–532. дои : 10.1007/s12532-018-0135-8 . S2CID   255616114 .
• Рефельдт, Д.; Кох, Т. (февраль 2023 г.). «Последствия, конфликты и сокращения для деревьев Штейнера» . Математическое программирование . 197 (2): 903–966. дои : 10.1007/s10107-021-01757-5 . S2CID   231842568 .
• Карпински, Марек; Зеликовский, Александр (1998). «Аппроксимация плотных случаев покрытия задач» . Материалы семинара DIMACS по проектированию сетей: возможности подключения и расположение объектов . Серия DIMACS по дискретной математике и теоретической информатике. Том. 40. Американское математическое общество. стр. 169–178.
• Корте, Бернхард ; Виген, Йенс (2006). «Раздел 20.1». Комбинаторная оптимизация: теория и алгоритмы (3-е изд.). Спрингер . ISBN  3-540-25684-9 .
• Коу, Л.; Марковский, Г.; Берман, Л. (1 июня 1981 г.). «Быстрый алгоритм для деревьев Штейнера». Акта Информатика . 15 (2): 141–145. дои : 10.1007/BF00288961 . S2CID   21057232 .
• Левин, А.Ю. (1971). «Алгоритм кратчайшего соединения группы вершин графа». Советские математические доклады . 12 : 1477–1481.
• Локштанов Даниил; Недерлоф, Йеспер (2010). «Экономия места за счет алгебраизации». Материалы 42-го симпозиума ACM по теории вычислений . стр. 321–330. дои : 10.1145/1806689.1806735 .
• Паолини, Э.; Степанов, Е. (2012). «Результаты существования и регулярности задачи Штейнера» (PDF) . Расчет Вар. Частичный Диф. Уравнения . 46 (3–4): 837–860. дои : 10.1007/s00526-012-0505-4 . hdl : 2158/600141 . S2CID   55793499 .
• Робинс, Габриэль; Зеликовский, Александр (2000). «Улучшенная аппроксимация дерева Штейнера в графах» . Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '00) . Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. стр. 770–779 . ISBN  0-89871-453-2 .
• Шервани, Навид А. (1993). Алгоритмы автоматизации физического проектирования СБИС . Академическое издательство Клувер. ISBN  9781475722192 .
• Смит, Дж. М.; Винтер, П. (1995). «Вычислительная геометрия и проектирование топологических сетей». В Ду, Дин-Чжу; Хван, Фрэнк (ред.). Вычисления в евклидовой геометрии . Серия конспектов лекций по вычислительной технике. Том. 4 (2-е изд.). Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., стр. 351–451. ISBN  981-02-1876-1 .
• Такахаси, Хиромицу; Мацуяма, Акира (1980). «Приближенное решение задачи Штейнера в графах». Математика. Японика . 24 (6): 573–577.
• Vazirani, Vijay V. (2003). Approximation Algorithms . Berlin: Springer. ISBN  3-540-65367-8 .
• Ву, Бан Е; Чао, Кун-Мао (2004). «Глава 7». Связующие деревья и проблемы оптимизации . Чепмен и Холл/CRC. ISBN  1-58488-436-3 .
• Ву, Ю.Ф.; Видмайер, П.; Вонг, К.К. (май 1986 г.). «Более быстрый алгоритм аппроксимации задачи Штейнера в графах». Акта Информатика . 23 (2): 223–229. дои : 10.1007/bf00289500 . S2CID   7772232 .

Внешние ссылки

• GeoSteiner (Программное обеспечение для решения задач евклидова и прямолинейного дерева Штейнера; исходный код доступен, бесплатен для некоммерческого использования)
• SCIP-Jack (Программное обеспечение для решения проблемы дерева Штейнера в графах и 14 вариантов, например, задача о дереве Штейнера, собирающая призы; бесплатно для некоммерческого использования)
• Подпрограмма Фортрана для нахождения вершины Штейнера треугольника (т. е. точки Ферма ), ее расстояний от вершин треугольника и относительных весов вершин.
• Филомурка (Решатель небольших задач о дереве Штейнера в графах)
• https://www.youtube.com/watch?v=PI6rAOWu-Og (Фильм: решение задачи о дереве Штейнера с помощью воды и мыла)
• Нурмохаммадпур, Мохаммад; Рагхавендра, Каулиджи С.; Рао, Шрирам; Кандула, Шрикант (2017), «Использование деревьев Штейнера для минимизации среднего времени завершения массовой передачи данных», DCCast: эффективная передача «точка-многоточка» между центрами обработки данных , Ассоциация USENIX, arXiv : 1707.02096
• Хазевинкель, М. (2001) [1994], «Проблема дерева Штейнера» , Энциклопедия математики , EMS Press
• М. Хауптманн, М. Карпински (2013): Сборник проблем дерева Штейнера