Вестник МГОУ. Серия: Физика-математика / 2015 №2

Название статьи СЕТИ ШТЕЙНЕРА С ПОДВИЖНОЙ ГРАНИЦЕЙ: СЛУЧАЙ ПРЯМОЙ И ПАРЫ ТОЧЕК
Авторы Птицына И.В.
Серия Физика-математика
Страницы 8 - 28
Аннотация Статья посвящена задаче построения минимальных сетей, связывающих дискретное множество точек и гладкую кривую или поверхность в евклидовом пространстве и явяется одним из обобщений проблемы Штейнера. В случае двух точек и прямой на евклидовой плоскости описаны множества расположений точек для всех типов абсолютно минимальных графов, а также минимальных остовных графов и графов Штейнера; вычислены длины всех видов минимальных графов и отношения длин графов Штейнера и длин минимальных остовных графов: множество таких отношений совпадает с множеством точек полуинтервала.
Ключевые слова проблема Штейнера, остовный граф, граф Штейнера, точка Штейнера, отношение Штейнера
Индекс УДК 514.774.8+519.176
DOI
Список цитируемой литературы 1. Иванов А.О., Тужилин А.А. Теория экстремальных сетей. Москва; Ижевск: Институт компьютерных исследований, 2003. С. 424.
2. R. Booth, D.A. Thomas, and J.F. Weng, Shortest Networks for One line and Two Points in Space // Advances in Steiner Trees edited by Ding-Zhu, J.M. Smith and J.H. Rubinstein, Kluwer Academic Publishers, Boston, London, 2000. P. 15-27.
Полный текст статьи pdf
Кол-во скачиваний 52

 

Яндекс цитирования Яндекс.Метрика Рейтинг@Mail.ru

   

© 2007 - 2018 Московский государственный областной университет

При цитировании ссылка на «Вестник МГОУ» обязательна. Воспроизведение материалов в печатных, электронных или иных изданиях, без разрешения редакции, запрещено. Опубликованные в журнале материалы могут использоваться только в некоммерческих целях.