Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №11, Москва, 2002
Авторы: Иванов А.О., Тужилин А.А.
Отношение Штейнера. Современное состояние
Аннотация:
Отношение Штейнера характеризует величину относительной ошибки приближения кратчайшего дерева, соединяющего конечное подмножество точек метрического пространства, минимальным остовным деревом в наихудшем возможном случае. Эта характеристика метрических пространств активно изучается с 60х годов прошлого века. В работе изложены современные (на 2002 год) результаты на эту тему, в том числе, обсуждаются пробелы в доказательстве гипотезы Джилберта—Поллака об отношении Штейнера евклидовой плоскости, представленной Венном и Ду.
Ключевые слова:
проблема Штейнера, отношение Штейнера, кратчайшая сеть, минимальное остовное дерево
Язык публикации: русский, страниц: 22 (с. 27-48)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Иванов Александр Олегович,  ,  механико-математический факультет МГУ
  • Тужилин Алексей Августинович,  механико-математический факультет МГУ