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

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

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

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

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

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

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

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

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

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

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

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

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

Задача о прямолинейном дереве Штейнера является вариантом геометрической задачи о дереве Штейнера на плоскости, в которой евклидово расстояние заменяется прямолинейным расстоянием . Задача возникает при физическом проектировании автоматизации электронного проектирования . В схемах VLSI прокладка проводов осуществляется проводами , которые часто ограничены правилами проектирования, чтобы проходить только в вертикальном и горизонтальном направлениях, поэтому задача о прямолинейном дереве Штейнера может использоваться для моделирования прокладки сетей с более чем двумя терминалами. ^[6]

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

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

Частным случаем этой проблемы является случай, когда G является полным графом , каждая вершина $v \in V$ соответствует точке в метрическом пространстве , а веса ребер w ( e ) для каждого e ∈ E соответствуют расстояниям в пространстве. Иначе говоря, веса ребер удовлетворяют неравенству треугольника . Этот вариант известен как задача метрического дерева Штейнера . Учитывая пример (неметрической) задачи дерева Штейнера, мы можем преобразовать его за полиномиальное время в эквивалентный пример задачи метрического дерева Штейнера; преобразование сохраняет фактор аппроксимации. ^[10]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отношение Штейнера — это супремум отношения общей длины минимального остовного дерева к минимальному дереву Штейнера для набора точек на евклидовой плоскости. ^[31]

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

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

Смотрите также

Примечания

^ Рехфельдт и Кох (2023).
^ Джул и др. (2018).
^ Маркус Бразил, Рональд Л. Грэм, Дорин А. Томас и Мартин Захариасен, «К истории проблемы евклидового дерева Штейнера», JSTOR 24569605
^ Корте, Бернхард ; Нешетржил, Ярослав (2001), «Работа Войтеха Ярника по комбинаторной оптимизации», Discrete Mathematics , 235 (1–3): 1–17, doi :10.1016/S0012-365X(00)00256-9, hdl : 10338.dmlcz/ 500662 , МР 1829832.
^ Крещенци и др. (2000).
^ Шервани (1993), стр. 228.
^ Любич, Ивана (2021). «Решение деревьев Штейнера: последние достижения, проблемы и перспективы». Networks . 77 (2): 177–204. doi :10.1002/net.22005. ISSN 1097-0037. S2CID 229458488.
^ Новак, Роман; Ругель, Йозеф; Кандус, Горазд (1 октября 2001 г.). «Заметка о распределенной многоадресной маршрутизации в сетях «точка-точка». Computers & Operations Research . 28 (12): 1149–1164. doi :10.1016/S0305-0548(00)00029-0. ISSN 0305-0548.
^ Климм, Флориан; Толедо, Энрике М.; Монфёга, Томас; Чжан, Фанг; Дин, Шарлотта М.; Рейнерт, Джесин (2 ноября 2020 г.). «Обнаружение функциональных модулей посредством интеграции данных секвенирования одноклеточной РНК с сетями белок-белкового взаимодействия». BMC Genomics . 21 (1): 756. doi : 10.1186/s12864-020-07144-2 . ISSN 1471-2164. PMC 7607865 . PMID 33138772.
^ Вазирани (2003), стр. 27–28.
^ ab Бирка и др. (2010).
^ Хлебик и Хлебикова (2008).
^ Берман, Карпински и Зеликовский (2009).
^ Карпински и Зеликовский (1998).
^ Смит и Винтер (1995), стр. 361.
^ Керивин, Эрве; Махджуб, А. Ридха (2005). «Проектирование живучих сетей: обзор». Networks . 46 (1): 1–21. doi :10.1002/net.20072. ISSN 0028-3045. S2CID 8165318.
^ Паолини и Степанов (2012).
^ Коу, Марковски и Берман (1981).
^ Такахаси и Мацуяма (1980).
^ Ву, Видмайер и Вонг (1986).
^ Дрейфус и Вагнер (1971).
^ Левин (1971).
^ Фукс и др. (2007).
^ Бьёрклунд и др. (2007).
^ Локштанов и Недерлоф (2010).
^ Фомин и др. (2015).
^ Cygan и др. (2016).
^ Дом, Локштанов и Саураб (2014).
^ Локштанов, Даниэль; Панолан, Фахад; Рамануджан, М.С.; Саурабх, Сакет (19 июня 2017 г.). «Lossy kernelization». Труды 49-го ежегодного симпозиума ACM SIGACT по теории вычислений (PDF) . STOC 2017. Нью-Йорк, США: Ассоциация вычислительной техники. стр. 224–237. doi :10.1145/3055399.3055456. ISBN 978-1-4503-4528-6. S2CID 14599219.
^ аб Дворжак, Павел; Фельдманн, Андреас Э.; Кноп, Душан; Масаржик, Томаш; Туфар, Томаш; Веселый, Павел (1 января 2021 г.). «Параметризованные схемы аппроксимации деревьев Штейнера с малым числом вершин Штейнера». SIAM Journal по дискретной математике . 35 (1): 546–574. arXiv : 1710.00668 . дои : 10.1137/18M1209489. ISSN 0895-4801. S2CID 3581913.
^ Гэнли (2004).
↑ The New York Times от 30 октября 1990 года сообщила, что доказательство найдено и что Рональд Грэм , предложивший за доказательство 500 долларов, собирается отправить авторам чек.
^ Иванов и Тужилин (2012).
^ Хван (1976).

Ссылки

Berman, Piotr; Karpinski, Marek ; Zelikovsky, Alexander (2009). "1.25-аппроксимационный алгоритм для задачи дерева Штейнера с расстояниями 1 и 2". Алгоритмы и структуры данных: 11-й международный симпозиум, WADS 2009, Банф, Канада, 21–23 августа 2009 г., Труды . Lecture Notes in Computer Science. Vol. 5664. pp. 86–97. arXiv : 0810.1851 . doi :10.1007/978-3-642-03367-4_8. ISBN 978-3-642-03366-7.
Берн, Маршалл В.; Грэм, Рональд Л. (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. ISBN 978-1-59593-631-8.
Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanita, L. (2010). «Улучшенная аппроксимация на основе LP для дерева Штейнера». Труды 42-го симпозиума ACM по теории вычислений . С. 583–592. CiteSeerX 10.1.1.177.3565 . doi :10.1145/1806689.1806769. ISBN 978-1-4503-0050-6.
Хлебик, Мирослав; Хлебикова, Янка (2008). «Проблема дерева Штейнера на графах: результаты о неаппроксимируемости». Теоретическая информатика . 406 (3): 207–214. дои : 10.1016/j.tcs.2008.06.046 .
Chung, FRK ; Graham, RL (1985). "Новая граница для минимальных деревьев Евклида Штейнера". Дискретная геометрия и выпуклость (Нью-Йорк, 1982) . Annals of the New York Academy of Science. Том 440. Нью-Йорк: New York Academy of Science. С. 328–346. Bibcode :1985NYASA.440..328C. doi :10.1111/j.1749-6632.1985.tb14564.x. MR 0809217.
Cieslik, Dietmar (1998). Минимальные деревья Штейнера . Springer. стр. 319. ISBN 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 Transactions on Algorithms . 11 (2): 13:1–13:20. doi :10.1145/2650261. S2CID 13570734.
Дрейфус, С. Э.; Вагнер, Р. А. (1971). «Проблема Штейнера в графах». Networks . 1 (3): 195–207. doi :10.1002/net.3230010302.
Фомин, Федор В.; Каски, Петтери; Локштанов, Даниэль; Панолан, Фахад; Саурабх, Сакет (2015). «Параметризованный одноэкспоненциальный по времени полиномиальный пространственный алгоритм для дерева Штейнера». Автоматы, языки и программирование – 42-й международный коллоквиум, ICALP 2015, Труды, часть I. Конспект лекций по информатике. Том 9134. С. 494–505. doi :10.1007/978-3-662-47672-7_40. hdl : 1956/23311 . ISBN 978-3-662-47671-0.
Фукс, Бенджамин; Керн, Уолтер; Мёлле, Даниэль; Рихтер, Стефан; Россманит, Питер; Ван, Синьхуэй (2007). «Динамическое программирование для минимальных деревьев Штейнера» (PDF) . Теория вычислительных систем . 41 (3): 493–500. дои : 10.1007/s00224-007-1324-4. S2CID 7478978.
Ganley, Joseph L. (2004). "Отношение Штейнера". In Black, Paul E. (ред.). Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий США . Получено 24 мая 2012 г.
Garey, Michael R .; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455. MR 0519066. OCLC 247570676., стр. 208–209, задачи ND12 и ND13.
Хванг, ФК (1976). «О минимальных деревьях Штейнера с прямолинейным расстоянием». Журнал SIAM по прикладной математике . 30 (1): 104–114. doi :10.1137/0130013.
Hwang, FK; Richards, DS; Winter, P. (1992). Проблема дерева Штейнера . Annals of Discrete Mathematics. Том 53. North-Holland : Elsevier . ISBN 0-444-89098-X.
Иванов, Александр; Тужилин, Алексей (1994). Минимальные сети: проблема Штейнера и ее обобщения . NW, Бока-Ратон, Флорида: CRC Press . ISBN 978-0-8493-8642-8.
Иванов, Александр; Тужилин, Алексей (2000). Разветвленные решения одномерных вариационных задач . Сингапур-Нью-Джерси-Лондон-Гонконг: World Scientific . ISBN 978-981-02-4060-8.
Иванов, Александр; Тужилин, Алексей (2003). Теория экстремальных сетей . Москва-Ижевск: Институт компьютерных исследований. ISBN 5-93972-292-X.
Иванов, Александр; Тужилин, Алексей (2012). «Гипотеза Гилберта–Поллака об отношении Штейнера все еще открыта: Уточняющее утверждение». Algorithmica . 62 (1–2): 630–632. doi :10.1007/s00453-011-9508-3. S2CID 7486839.
Иванов, Александр; Тужилин, Алексей (2015). «Разветвленные покрытия и отношение Штейнера». Международные труды по исследованию операций . 23 (5): 875–882. arXiv : 1412.5433 . doi :10.1111/itor.12182. S2CID 3386263.
Juhl, D.; Warme, DM; Winter, P.; Zachariasen, M. (январь 2018 г.). «Пакет программного обеспечения GeoSteiner для вычисления деревьев Штейнера на плоскости: обновленное вычислительное исследование». Mathematical Programming Computation . 10 (4): 487–532. doi :10.1007/s12532-018-0135-8. S2CID 255616114.
Рехфельдт, Д.; Кох, Т. (февраль 2023 г.). «Импликации, конфликты и сокращения для деревьев Штейнера». Математическое программирование . 197 (2): 903–966. doi : 10.1007/s10107-021-01757-5 . S2CID 231842568.
Карпински, Марек; Зеликовский, Александр (1998). «Аппроксимация плотных случаев задач покрытия». Труды семинара DIMACS по проектированию сетей: связность и расположение объектов . Серия DIMACS по дискретной математике и теоретической информатике. Том 40. Американское математическое общество. С. 169–178.
Корте, Бернхард ; Виген, Йенс (2006). "Раздел 20.1". Комбинаторная оптимизация: теория и алгоритмы (3-е изд.). Springer . 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. doi :10.1145/1806689.1806735. ISBN 978-1-4503-0050-6.
Паолини, Э.; Степанов, Э. (2012). "Результаты существования и регулярности для проблемы Штейнера" (PDF) . Calc. Var. Partial Diff. Equations . 46 (3–4): 837–860. doi :10.1007/s00526-012-0505-4. hdl : 2158/600141 . S2CID 55793499.
Робинс, Габриэль; Зеликовский, Александр (2000). «Улучшенная аппроксимация дерева Штейнера в графах». Труды одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '00). Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. стр. 770–779. ISBN 0-89871-453-2.
Шервани, Навид А. (1993). Алгоритмы для автоматизации физического проектирования СБИС . Kluwer Academic Publishers. ISBN 9781475722192.
Смит, Дж. М.; Винтер, П. (1995). «Вычислительная геометрия и топологическое проектирование сетей». В Ду, Дин-Чжу; Хван, Фрэнк (ред.). Вычисления в евклидовой геометрии . Серия заметок лекций по вычислениям. Том 4 (2-е изд.). Ривер Эдж, Нью-Джерси: World Scientific Publishing Co. стр. 351–451. ISBN 981-02-1876-1.
Такахаси, Хиромицу; Мацуяма, Акира (1980). «Приближенное решение проблемы Штейнера в графах». Math. Japonica . 24 (6): 573–577.
Вазирани, Виджай В. (2003). Алгоритмы аппроксимации . Берлин: Шпрингер. ISBN 3-540-65367-8.
Wu, Bang Ye; Chao, Kun-Mao (2004). "Глава 7". Spanning Trees and Optimization Problems . Chapman & Hall/CRC. ISBN 1-58488-436-3.
Wu, YF; Widmayer, P.; Wong, CK (май 1986). «Быстрый алгоритм приближения для задачи Штейнера в графах». Acta Informatica . 23 (2): 223–229. doi :10.1007/bf00289500. S2CID 7772232.

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

На Викискладе есть медиафайлы по теме «Проблема дерева Штейнера» .

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