Оптимальные сети

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