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

Translated title of the contribution: Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

В статье предлагаются полиномиальные приближенные алгоритмы с константным фактором аппроксимации для задачи пересечения заданного набора отрезков на плоскости наименьшим числом одинаковых кругов. Если число различных направлений отрезков, входящих в набор, не превосходит , для этой задачи известен простой -приближенный алгоритм с временной сложностью Также для случая задачи на множествах ребер произвольных плоских графов известен 100-приближенный алгоритм с временем работы . В настоящей работе для частных случаев задачи на множествах ребер графов Габриеля, графов относительных окрестностей и минимальных евклидовых остовных деревьев, число различных ориентаций ребер в которых, вообще говоря, не ограничено сверху, удается построить несложные алгоритмы с факторами аппроксимации, равными соответственно 14, 12 и 10, имеющие существенно меньшую трудоемкость по сравнению с вышеупомянутым алгоритмом для общего случая задачи на множествах ребер произвольных плоских графов.
Translated title of the contributionApproximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks
Original languageRussian
Pages (from-to)62-77
Number of pages16
JournalТруды института математики и механики УрО РАН
Volume25
Issue number1
DOIs
Publication statusPublished - 2019

Keywords

  • combinatorial optimization
  • approximation algorithm
  • geometric Hitting Set problem on the plane
  • straight line segment
  • Gabriel graph
  • relative neighborhood graph
  • Euclidean minimum spanning tree

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

Fingerprint Dive into the research topics of 'Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks'. Together they form a unique fingerprint.

Cite this