ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Connectivity with uncertainty regions given as line segments
    Cabello, Sergio ; Gajser, David, 1987-
    For a set ▫${\mathcal Q}$▫ of points in the plane and a real number ▫$\delta \ge 0$▫, let ▫$\mathbb{G}_\delta({\mathcal Q})$▫ be the graph defined on ▫${\mathcal Q}$▫ by connecting each pair of ... points at distance at most ▫$\delta$▫. We consider the connectivity of ▫$\mathbb{G}_\delta({\mathcal 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 ▫${\mathcal P}$▫ of ▫$n-k$▫ points in the plane and a set ▫${\mathcal S}$▫ of ▫$k$▫ line segments in the plane, find the minimum ▫$\delta \ge 0$▫ with the property that we can select one point ▫$p_s\in s$▫ for each segment ▫$s\in {\mathcal S}$▫ and the corresponding graph ▫$\mathbb{G}_\delta( {\mathcal P}\cup \{ p_s\mid s\in {\mathcal S}\})$▫ is connected. It is known that the problem is NP-hard. We provide an algorithm to exactly compute an optimal solution in ▫${\mathcal O}(f(k) n \log n)$▫ time, for a computable function ▫$f(\cdot)$▫. This implies that the problem is FPT when parameterized by ▫$k$▫. The best previous algorithm uses ▫${\mathcal O}((k!)^k k^{k+1}\cdot n^{2k})$▫ time and computes the solution up to fixed precision.
    Source: Algorithmica. - ISSN 0178-4617 (Vol. 86, iss. 5, May 2024, str. 1512-1544)
    Type of material - article, component part ; adult, serious
    Publish date - 2024
    Language - english
    COBISS.SI-ID - 180364547

    Link(s):

    Repository of the University of Ljubljana – RUL
    DiRROS - Digital repository of Slovenian research organizations
    DOI

source: Algorithmica. - ISSN 0178-4617 (Vol. 86, iss. 5, May 2024, str. 1512-1544)
loading ...
loading ...
loading ...

Shelf entry