Проблема дерева Штейнера
О коротких соединительных сетях с добавленными вершинами

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

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

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

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

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

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

Первоначальная задача была сформулирована в форме, которая стала известна как задача евклидова дерева Штейнера или геометрическая задача дерева Штейнера : даны 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  ⊆  V — подмножество вершин, называемых терминалами . Дерево Штейнера — это дерево в G , охватывающее S . Существует две версии задачи: в задаче оптимизации, связанной с деревьями Штейнера, задача состоит в том, чтобы найти дерево Штейнера с минимальным весом; в задаче принятия решения веса ребер являются целыми числами, а задача состоит в том, чтобы определить, существует ли дерево Штейнера, общий вес которого не превышает предопределенного натурального числа k . Задача принятия решения является одной из 21 NP-полной задачи Карпа ; следовательно, задача оптимизации является NP-трудной . Задачи о дереве Штейнера в графах применяются к различным проблемам в исследованиях и промышленности, [7] включая многоадресную маршрутизацию [8] и биоинформатику. [9]

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

В то время как евклидова версия допускает PTAS, известно, что метрическая задача дерева Штейнера является APX-полной , т. е., если P = NP , невозможно достичь коэффициентов аппроксимации, которые сколь угодно близки к 1 за полиномиальное время. Существует алгоритм с полиномиальным временем, который аппроксимирует минимальное дерево Штейнера с точностью до множителя ; [11] однако, аппроксимация в пределах множителя является NP-трудной. [12] Для ограниченного случая задачи дерева Штейнера с расстояниями 1 и 2 известен алгоритм аппроксимации 1,25. [13] Карпинский и Александр Зеликовский построили PTAS для плотных экземпляров задач дерева Штейнера. [14] вн ⁡ ( 4 ) + ε ≈ 1.386 {\displaystyle \ln(4)+\varepsilon \approx 1.386} 96 / 95 ≈ 1.0105 {\displaystyle 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] вн ⁡ ( 4 ) + ε ≤ 1.39 {\displaystyle \ln(4)+\varepsilon \leq 1.39}

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. ^ Рехфельдт и Кох (2023).
  2. ^ Джул и др. (2018).
  3. ^ Маркус Бразил, Рональд Л. Грэм, Дорин А. Томас и Мартин Захариасен, «К истории проблемы евклидового дерева Штейнера», JSTOR  24569605
  4. ^ Корте, Бернхард ; Нешетржил, Ярослав (2001), «Работа Войтеха Ярника по комбинаторной оптимизации», Discrete Mathematics , 235 ( 1–3 ): 1–17 , doi :10.1016/S0012-365X(00)00256-9, hdl : 10338.dmlcz/500662 , MR  1829832.
  5. ^ Крещенци и др. (2000).
  6. ^ Шервани (1993), стр. 228.
  7. ^ Любич, Ивана (2021). «Решение деревьев Штейнера: последние достижения, проблемы и перспективы». Networks . 77 (2): 177– 204. doi :10.1002/net.22005. ISSN  1097-0037. S2CID  229458488.
  8. ^ Новак, Роман; Ругель, Йозеф; Кандус, Горазд (1 октября 2001 г.). «Заметка о распределенной многоадресной маршрутизации в сетях точка-точка». Computers & Operations Research . 28 (12): 1149– 1164. doi :10.1016/S0305-0548(00)00029-0. ISSN  0305-0548.
  9. ^ Климм, Флориан; Толедо, Энрике М.; Монфёга, Томас; Чжан, Фанг; Дин, Шарлотта М.; Рейнерт, Джесин (2 ноября 2020 г.). «Обнаружение функциональных модулей посредством интеграции данных секвенирования одноклеточной РНК с сетями белок-белкового взаимодействия». BMC Genomics . 21 (1): 756. doi : 10.1186/s12864-020-07144-2 . ISSN  1471-2164. PMC 7607865 . PMID  33138772. 
  10. ^ Вазирани (2003), стр. 27–28.
  11. ^ ab Бирка и др. (2010).
  12. ^ Хлебик и Хлебикова (2008).
  13. ^ Берман, Карпински и Зеликовский (2009).
  14. ^ Карпински и Зеликовский (1998).
  15. ^ Смит и Винтер (1995), стр. 361.
  16. ^ Керивин, Эрве; Махджуб, А. Ридха (2005). «Проектирование живучих сетей: обзор». Networks . 46 (1): 1– 21. doi :10.1002/net.20072. ISSN  0028-3045. S2CID  8165318.
  17. ^ Паолини и Степанов (2012).
  18. ^ Коу, Марковски и Берман (1981).
  19. ^ Такахаши и Мацуяма (1980).
  20. ^ Ву, Видмайер и Вонг (1986).
  21. ^ Дрейфус и Вагнер (1971).
  22. ^ Левин (1971).
  23. ^ Фукс и др. (2007).
  24. ^ Бьёрклунд и др. (2007).
  25. ^ Локштанов и Недерлоф (2010).
  26. ^ Фомин и др. (2015).
  27. ^ Cygan и др. (2016).
  28. ^ Дом, Локштанов и Саураб (2014).
  29. ^ Локштанов, Даниэль; Панолан, Фахад; Рамануджан, М.С.; Саурабх, Сакет (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.
  30. ^ аб Дворжак, Павел; Фельдманн, Андреас Э.; Кноп, Душан; Масаржик, Томаш; Туфар, Томаш; Веселый, Павел (1 января 2021 г.). «Параметризованные схемы аппроксимации деревьев Штейнера с малым числом вершин Штейнера». SIAM Journal по дискретной математике . 35 (1): 546–574 . arXiv : 1710.00668 . дои : 10.1137/18M1209489. ISSN  0895-4801. S2CID  3581913.
  31. ^ Гэнли (2004).
  32. ↑ The New York Times от 30 октября 1990 года сообщила, что доказательство найдено и что Рональд Грэм , предложивший за доказательство 500 долларов, собирается отправить авторам чек.
  33. ^ Иванов и Тужилин (2012).
  34. ^ Хван (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. 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 . doi : 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 . doi : 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.
  • Hwang, FK (1976). «О минимальных деревьях Штейнера с прямолинейным расстоянием». SIAM Journal on Applied Mathematics . 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 . doi : 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): Сборник задач о дереве Штейнера
Retrieved from "https://en.wikipedia.org/w/index.php?title=Steiner_tree_problem&oldid=1265880984"