Аннотация
В работе изучается вычислительная сложность и строятся точные полиномиальные алгоритмы для задачи оптимального пересечения заданного набора отрезков на плоскости минимальным числом одинаковых кругов радиуса > 0, при этом отрезки задают множество ребер некоторого плоского графа и пересекаются не более чем в своих концевых точках. Близкие геометрические задачи возникают при анализе безопасности физических сетей. В работе сообщается -трудность задачи в сильном смысле для семейств отрезков, порождаемых триангуляциями Делоне, графами Габриеля и некоторыми другими их подграфами, часто возникающими в проектировании сетей, для и некоторой константы , где и являются (евклидовыми) длинами наидлиннейшего и наикратчайшего ребер графа .
Переведенное название | Computational complexity for the problem of optimal intersections of straight line segments by disks |
---|---|
Язык оригинала | Русский |
Страницы (с-по) | 171-181 |
Число страниц | 11 |
Журнал | Труды института математики и механики УрО РАН |
Том | 23 |
Номер выпуска | 3 |
DOI | |
Состояние | Опубликовано - 2017 |
Предметные области WoS
- Математика, Прикладная
ГРНТИ
- 50.05.00 Теоретические основы программирования
Уровень публикации
- Перечень ВАК