ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ ЗАДАЧИ ОПТИМАЛЬНОГО ПЕРЕСЕЧЕНИЯ ОТРЕЗКОВ КРУГАМИ

Translated title of the contribution: Computational complexity for the problem of optimal intersections of straight line segments by disks

Research output: Contribution to journalArticle

Abstract

В работе изучается вычислительная сложность и строятся точные полиномиальные алгоритмы для задачи оптимального пересечения заданного набора отрезков на плоскости минимальным числом одинаковых кругов радиуса > 0, при этом отрезки задают множество ребер некоторого плоского графа и пересекаются не более чем в своих концевых точках. Близкие геометрические задачи возникают при анализе безопасности физических сетей. В работе сообщается -трудность задачи в сильном смысле для семейств отрезков, порождаемых триангуляциями Делоне, графами Габриеля и некоторыми другими их подграфами, часто возникающими в проектировании сетей, для и некоторой константы , где и являются (евклидовыми) длинами наидлиннейшего и наикратчайшего ребер графа .
Translated title of the contributionComputational complexity for the problem of optimal intersections of straight line segments by disks
Original languageRussian
Pages (from-to)171-181
Number of pages11
JournalТруды института математики и механики УрО РАН
Volume23
Issue number3
DOIs
Publication statusPublished - 2017

Keywords

  • computational complexity
  • Hitting Set Problem
  • Continuous Disk Cover problem
  • Delaunay triangulations
  • OPTIMAL-ALGORITHMS
  • GRAPHS

WoS ResearchAreas Categories

  • Mathematics, Applied

GRNTI

  • 50.05.00

Level of Research Output

  • VAK List

Cite this