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

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

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

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

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

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

Евклидово дерево Штейнера [ править ]

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

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

Проблема для N = 3 рассматривалась давно и быстро расширилась до задачи поиска звездообразной сети с одним концентратором, подключенным ко всем из N заданных точек, минимальной общей длины. Однако, хотя полная проблема дерева Штайнера была сформулирована в письме Гаусса , ее первое серьезное рассмотрение было в статье 1934 года, написанной на чешском языке Войтехом Ярником и Милошем Кёсслером [ cs ] . Эта статья долгое время игнорировалась, но она уже содержит «практически все общие свойства деревьев Штейнера», позже приписываемые другим исследователям, включая обобщение проблемы с плоскости на более высокие измерения. ^[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] ${\ Displaystyle \ ln (4) + \ varepsilon \ приблизительно 1,386}$ ${\ displaystyle 96/95 \ приблизительно 1.0105}$

В особом случае задачи графа, задача дерева Штейнера для квази-двудольный графов , 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 / t из Коу и др.

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

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

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

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

Коэффициент Штейнера [ править ]

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

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

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

См. Также [ править ]

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

Примечания [ править ]

^ "Отчет Пользина и Вахдати Данешманд" (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) .
^ Chlebík & Chlebíková (2008) .
^ Берман, Карпинский и Зеликовский (2009) .
^ Карпинский и Zelikovsky (1998) .
^ Смит и Винтер (1995) , стр. 361.
^ Паолини и Степанов (2012) .
^ Коу, Марковский & Berman (1981) .
Перейти ↑ Takahashi & Matsuyama (1980) .
^ У, Widmayer & Wong (1986) .
^ Дрейфус и Вагнер .
↑ Левин .
^ Fuchs et al .
^ Björklund et al .
^ Локштанов и Недерлоф .
^ Фомин и др .
^ Cygan et al .
^ Дом, Lokshtanov & Саурабй .
^ Ganley (2004) .
↑ 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 .CS1 maint: ref=harv (link)
Берн, Маршалл В .; Грэм, Рональд Л. (1989). «Задача кратчайшей сети». Scientific American . 260 (1): 84–89. Bibcode : 1989SciAm.260a..84B . DOI : 10.1038 / Scientificamerican0189-84 .CS1 maint: ref=harv (link)
Бьёрклунд, Андреас; Хусфельдт, Тор; Каски, Петтери; Койвисто, Микко (2007). «Фурье встречает Мёбиуса: быстрая свертка подмножества». Материалы 39-го симпозиума ACM по теории вычислений . С. 67–74. arXiv : cs / 0611101 . DOI : 10.1145 / 1250790.1250801 .
Byrka, J .; Grandoni, F .; Rothvoß, T .; Санита, Л. (2010). «Улучшенное приближение на основе LP для дерева Штейнера». Материалы 42-го симпозиума ACM по теории вычислений . С. 583–592. CiteSeerX 10.1.1.177.3565 . DOI : 10.1145 / 1806689.1806769 .CS1 maint: ref=harv (link)
Хлебик, Мирослав; Хлебикова, Янка (2008). «Проблема дерева Штейнера на графах: результаты о несовместимости». Теоретическая информатика . 406 (3): 207–214. DOI : 10.1016 / j.tcs.2008.06.046 .CS1 maint: ref=harv (link)
Чанг, ФРК ; Грэм, Р.Л. (1985). «Новая оценка евклидовых минимальных деревьев Штейнера». Дискретная геометрия и выпуклость (Нью-Йорк, 1982) . Анналы Нью-Йоркской академии наук. 440 . Нью-Йорк: Нью-Йоркская академия наук. С. 328–346. Bibcode : 1985NYASA.440..328C . DOI : 10.1111 / j.1749-6632.1985.tb14564.x . Руководство по ремонту 0809217 .CS1 maint: ref=harv (link)
Чеслик, Дитмар (1998). Минимальные деревья Штайнера . п. 319. ISBN 0-7923-4983-0.
Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпинский, Марек ; Woeginger, Герхард (2000). «Минимальное геометрическое дерево Штейнера» . Сборник задач оптимизации NP .CS1 maint: ref=harv (link)
Циган, Марек; Делл, Хольгер; Локштанов Даниил; Маркс, Даниэль; Недерлоф, Джеспер; Окамото, Ёсио; Патури, Рамамохан; Саураб, Сакет; Вальстрём, Магнус (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 года .CS1 maint: ref=harv (link)
Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5, стр. 208–209, задачи ND12 и ND13.
Хван, Ф. К. (1976). «О минимальных деревьях Штейнера с прямолинейным расстоянием». Журнал SIAM по прикладной математике . 30 (1): 104–114. DOI : 10.1137 / 0130013 .CS1 maint: ref=harv (link)
Hwang, FK; Ричардс, Д.С. Уинтер, П. (1992). Проблема дерева Штейнера . Анналы дискретной математики. 53 . Северная Голландия : Эльзевир . 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). «Гипотеза отношения Штейнера Гилберта-Поллака все еще открыта: уточняющее заявление». Алгоритмика . 62 (1–2): 630–632. DOI : 10.1007 / s00453-011-9508-3 . S2CID 7486839 .CS1 maint: ref=harv (link)
Иванов, Александр; Тужилин, Алексей (2015). «Разветвленные покрытия и коэффициент Штейнера». Международные операции в операционных исследованиях (ITOR) . 23 (5): 875–882. arXiv : 1412,5433 . DOI : 10.1111 / itor.12182 . S2CID 3386263 .CS1 maint: ref=harv (link)
Juhl, D .; Warme, DM; Winter, P .; Захариасен, М. (2014). «Программный пакет GeoSteiner для вычисления деревьев Штейнера на плоскости: обновленное вычислительное исследование». Материалы 11-го конкурса по внедрению DIMACS (PDF) .CS1 maint: ref=harv (link)
Карпинский, Марек; Зеликовский, Александр (1998). «Аппроксимация плотных случаев покрывающих задач» . Труды семинара DIMACS по проектированию сетей: возможность подключения и расположение объектов . Серия DIMACS по дискретной математике и теоретической информатике. 40 . Американское математическое общество. С. 169–178.CS1 maint: ref=harv (link)
Корте, Бернхард ; Выген, Йенс (2006). «Раздел 20.1». Комбинаторная оптимизация: теория и алгоритмы (3-е изд.). Springer . ISBN 3-540-25684-9.
Kou, L .; Марковский, Г .; Берман, Л. (1 июня 1981 г.). «Быстрый алгоритм для деревьев Штейнера». Acta Informatica . 15 (2): 141–145. DOI : 10.1007 / BF00288961 .
Левин, А.Ю. (1971). «Алгоритм кратчайшего соединения группы вершин графа». Советские математические доклады . 12 : 1477–1481.
Локштанов Даниил; Недерлоф, Джеспер (2010). «Экономия места за счет алгебраизации». Материалы 42-го симпозиума ACM по теории вычислений . С. 321–330. DOI : 10.1145 / 1806689.1806735 .
Паолини, Э .; Степанов, Е. (2012). "Существование и регулярность результатов для проблемы Штейнера" (PDF) . Расчет. Вар. Частичная разница. Уравнения . 46 (3–4): 837–860. DOI : 10.1007 / s00526-012-0505-4 . ЛВП : 2158/600141 . S2CID 55793499 .CS1 maint: ref=harv (link)
Робинс, Габриэль; Зеликовский, Александр (2000). «Улучшенное приближение дерева Штейнера в графах» . Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '00) . Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. С. 770–779 . ISBN 0-89871-453-2.
Шервани, Навид А. (1993). Алгоритмы автоматизации физического проектирования СБИС . Kluwer Academic Publishers. ISBN 9781475722192.CS1 maint: ref=harv (link)
Смит, JM; Уинтер, П. (1995). «Вычислительная геометрия и топологическое проектирование сетей». Ин Ду, Дин-Чжу; Хван, Фрэнк (ред.). Вычисления в евклидовой геометрии . Серия конспектов лекций по вычислениям. 4 (2-е изд.). Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., стр. 351–451. ISBN 981-02-1876-1.CS1 maint: ref=harv (link)
Такахаши, Хиромицу; Мацуяма, Акира (1980). «Приближенное решение проблемы Штейнера в графах». Математика. Japonica . 24 (6): 573–577.
Вазирани, Виджай В. (2003). Аппроксимационные алгоритмы . Берлин: Springer. ISBN 3-540-65367-8.CS1 maint: ref=harv (link)
Ву, Банг Е; Чао, Кунь-Мао (2004). «Глава 7». Связующие деревья и проблемы оптимизации . Чепмен и Холл / CRC. ISBN 1-58488-436-3.
Wu, YF; Widmayer, P .; Вонг, СК (май 1986 г.). «Более быстрый алгоритм приближения для задачи Штейнера в графах». Acta Informatica . 23 (2): 223–229. DOI : 10.1007 / bf00289500 .

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с проблемой дерева Штейнера .

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 (Фильм: решение проблемы дерева Штейнера водой и мылом)
«Использование деревьев Штайнера для минимизации среднего времени завершения массовых передач данных», DCCast: эффективная передача данных между двумя центрами обработки данных , ассоциация USENIX

[1] "Отчет Пользина и Вахдати Данешманд" (PDF) . Проверено 11 ноября +2016 .

[FOOTNOTEJuhlWarmeWinterZachariasen2014-2] Juhl et al. (2014) .

[3] Корте, Бернхард ; Нешетржил, Ярослав (2001), «Работа Войтеха Ярника по комбинаторной оптимизации», Дискретная математика , 235 (1–3): 1–17, doi : 10.1016 / S0012-365X (00) 00256-9 , hdl : 10338.dmlcz / 500662 , Руководство по ремонту 1829832 .

[FOOTNOTECrescenziKannHalldórssonKarpinski2000-4] Crescenzi et al. (2000) .

[FOOTNOTESherwani1993228-5] Шервани (1993) , стр. 228.

[FOOTNOTEVazirani200327–28-6] Вазирани (2003) , стр. 27-28.

[FOOTNOTEByrkaGrandoniRothvoßSanita2010-7] а б Byrka et al. (2010) .

[FOOTNOTEChlebíkChlebíková2008-8] Chlebík & Chlebíková (2008) .

[FOOTNOTEBermanKarpinskiZelikovsky2009-9] Берман, Карпинский и Зеликовский (2009) .

[FOOTNOTEKarpinskiZelikovsky1998-10] Карпинский и Zelikovsky (1998) .

[FOOTNOTESmithWinter1995361-11] Смит и Винтер (1995) , стр. 361.

[FOOTNOTEPaoliniStepanov2012-12] Паолини и Степанов (2012) .

[FOOTNOTEKouMarkowskyBerman1981-13] Коу, Марковский & Berman (1981) .

[FOOTNOTETakahashiMatsuyama1980-14] Перейти ↑ Takahashi & Matsuyama (1980) .

[FOOTNOTEWuWidmayerWong1986-15] У, Widmayer & Wong (1986) .

[FOOTNOTEDreyfusWagner-16] Дрейфус и Вагнер .

[FOOTNOTELevin-17] Левин .

[FOOTNOTEFuchsKernMölleRichter-18] Fuchs et al .

[FOOTNOTEBjörklundHusfeldtKaskiKoivisto-19] Björklund et al .

[FOOTNOTELokshtanovNederlof-20] Локштанов и Недерлоф .

[FOOTNOTEFominKaskiLokshtanovPanolan-21] Фомин и др .

[FOOTNOTECyganDellLokshtanovMarx-22] Cygan et al .

[FOOTNOTEDomLokshtanovSaurabh-23] Дом, Lokshtanov & Саурабй .

[FOOTNOTEGanley2004-24] Ganley (2004) .

[25] New York Times от 30 октября 1990 г. сообщила, что доказательство было найдено и что Рональд Грэм , предложивший 500 долларов за доказательство, собирался отправить авторам чек по почте.

[FOOTNOTEIvanovTuzhilin2012-26] Иванов и Тужилин (2012) .

[FOOTNOTEHwang1976-27] Хван (1976) .

[1]