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

科研成果: Article

1 引用 (Scopus)

摘要

В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.
投稿的翻译标题Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks
源语言Russian
页(从-至)62-77
页数16
期刊Труды института математики и механики УрО РАН
25
1
DOI
Published - 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

指纹 探究 'ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ГАРАНТИРОВАННЫМИ ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ РЕБЕР НЕКОТОРЫХ МЕТРИЧЕСКИХ ГРАФОВ РАВНЫМИ КРУГАМИ' 的科研主题。它们共同构成独一无二的指纹。

引用此