|
|
Семинар отдела математического программирования
13 ноября 2015 г. 11:30–12:30, г. Екатеринбург, ул. Софьи Ковалевской, 16, актовый зал, 3 этаж, Институт математики и механики им. Н.Н.Красовского
|
 |
|
 |
|
|
|
Сложность и неприближаемость некоторых задач о наименьшей системе секущих объектов на геометрических графах
К. С. Кобылкинab
a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
|
| Количество просмотров: |
| Эта страница: | 130 | | Материалы: | 2 |
|
Аннотация:
В докладе рассматривается задача о наименьшей системе секущих объектов (geometric stabbers) для системы отрезков, совпадающих с ребрами некоторого геометрического графа $G.$ Даются результаты о сложности и неаппроксимируемости (нижние оценки для разрыва целочисленности) этих задач как в случае произвольного, так и важном для приложений частном случае планарного графа $G,$ где класс секущих объектов совпадает либо с множеством кругов фиксированного радиуса, либо с классом прямых произвольной ориентации.
|
|
Обратная связь: