Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101742
Title: Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks
Приближенные алгоритмы с гарантированными оценками точности для пересечения множеств ребер некоторых метрических графов равными кругами
Authors: Kobylkin, K. S.
Issue Date: 2019
Publisher: Krasovskii Institute of Mathematics and Mechanics
Citation: Kobylkin K. S. Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks / K. S. Kobylkin. — DOI 10.21538/0134-4889-2019-25-1-62-77 // Trudy Instituta Matematiki i Mekhaniki UrO RAN. — 2019. — Vol. 25. — Iss. 1. — P. 62-77.
Abstract: Polynomial-time approximation algorithms with constant approximation ratio are proposed for the problem of intersection of a given set of n planar straight line segments with the least number of equal disks. In the case where the segments have at most k different orientations, a simple 4k-approximate algorithm with time complexity O(n log n) is known. In addition, a 100-approximate algorithm with time complexity O(n4 log n) is known for the case of the problem on the edge sets of plane graphs. In this paper, for instances of the problem on the edge sets of Gabriel graphs, relative neighbourhood graphs, and Euclidean minimum spanning trees, in which the number of different edge orientations is, in general, unbounded, we construct simple O(n2)-time approximation algorithms with approximation ratios 14, 12, and 10, respectively. These algorithms outperform the aforementioned approximation algorithm for the general setting of the problem for edge sets of plane graphs. © 2019 Krasovskii Institute of Mathematics and Mechanics. All rights reserved.
Keywords: APPROXIMATION ALGORITHM
COMBINATORIAL OPTIMIZATION
EUCLIDEAN MINIMUM SPANNING TREE
GABRIEL GRAPH
GEOMETRIC HITTING SET PROBLEM ON THE PLANE
RELATIVE NEIGHBORHOOD GRAPH
STRAIGHT LINE SEGMENT
URI: http://hdl.handle.net/10995/101742
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85067669250
PURE ID: 9205765
ISSN: 1344889
DOI: 10.21538/0134-4889-2019-25-1-62-77
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85067669250.pdf285,54 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.