Connectivity with Uncertainty Regions Given as Line Segments.
Algorithmica
; 86(5): 1512-1544, 2024.
Article
em En
| MEDLINE
| ID: mdl-38650952
ABSTRACT
For a set Q of points in the plane and a real number δ≥0, let Gδ(Q) be the graph defined on Q by connecting each pair of points at distance at most δ.We consider the connectivity of Gδ(Q) in the best scenario when the location of a few of the points is uncertain, but we know for each uncertain point a line segment that contains it. More precisely, we consider the following optimization problem:
given a set P of n-k points in the plane and a set S of k line segments in the plane, find the minimum δ≥0 with the property that we can select one point ps∈s for each segment s∈S and the corresponding graph Gδ(Pâª{psâ£s∈S}) is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in O(f(k)nlogn) time, for a computable function f(·). This implies that the problem is FPT when parameterized by k. The best previous algorithm uses O((k!)kkk+1·n2k) time and computes the solution up to fixed precision.
Texto completo:
1
Base de dados:
MEDLINE
Idioma:
En
Ano de publicação:
2024
Tipo de documento:
Article