Приближенные алгоритмы с гарантированными оценками точности для пересечения множеств ребер некоторых метрических графов равными кругами
| Autor: | Kobylkin, K. S. |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
EUCLIDEAN MINIMUM SPANNING TREE
Applied Mathematics General Mathematics STRAIGHT LINE SEGMENT Computational Mechanics APPROXIMATION ALGORITHM COMBINATORIAL OPTIMIZATION GEOMETRIC HITTING SET PROBLEM ON THE PLANE RELATIVE NEIGHBORHOOD GRAPH MathematicsofComputing_DISCRETEMATHEMATICS GABRIEL GRAPH Computer Science Applications |
| Zdroj: | Tr. Inst. Mat. Meh. UrO RAN Trudy Instituta Matematiki i Mekhaniki UrO RAN |
| ISSN: | 0134-4889 |
| DOI: | 10.21538/0134-4889-2019-25-1-62-77 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|