Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Задача получила своё название...

Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм описан Джозефом Краскалом[англ.] в 1956 году, этот алгоритм...

длин рёбер. Задача о дереве Штейнера является NP-полной. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 23. Минимальные остовные деревья // Алгоритмы:...

версию классической задачи Штейнера о минимальном дереве (одной из 21 NP-полных задач Карпа), где вместо минимизации размера дерева целью является минимизация...

была минимальна? Задача Штейнера о минимальном дереве. Пусть имеется произвольное подмножество вершин связного взвешенного графа. Найти подграф-дерево с...

Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого...

(англ. Exact cover) задача о вершинном покрытии в гиперграфах (англ. Vertex cover in hypergraphs) задача Штейнера о минимальном дереве (англ. Steiner tree...

задачи, такие как задача о независимом множестве, задача о клике, раскраска, задача о кликовом покрытии, доминирующее множество и задача Штейнера о минимальном...

Квазидвудольным называется случай задачи Штейнера о минимальном дереве (состоящей из неориентированного графа G и множества R терминальных вершин), в котором...

алгоритм для решения задачи Штейнера о минимальном дереве (и в последующие годы более точные алгоритмы) и теорему уменьшения высоты дерева (Zelikovsky's height...

обязательно должно быть независимым от размеров задачи, но верхняя граница времени работы должна. Например, задача «обменять значения a {\displaystyle a} и b...