ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ РЕБЕР НЕКОТОРЫХ МЕТРИЧЕСКИХ ГРАФОВ РАВНЫМИ КРУГАМИ

Resultado de la investigación: Article

1 Cita (Scopus)

Resumen

В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.
Título traducido de la contribuciónApproximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks
Idioma originalRussian
Páginas (desde-hasta)62-77
Número de páginas16
PublicaciónТруды института математики и механики УрО РАН
Volumen25
N.º1
DOI
EstadoPublished - 2019

ASJC Scopus subject areas

  • Applied Mathematics
  • Mathematics(all)
  • Computer Science Applications
  • Computational Mechanics

WoS ResearchAreas Categories

  • Mathematics, Applied

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Huella Profundice en los temas de investigación de 'ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ РЕБЕР НЕКОТОРЫХ МЕТРИЧЕСКИХ ГРАФОВ РАВНЫМИ КРУГАМИ'. En conjunto forman una huella única.

Citar esto