VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Maximum matchings in geometric intersection graphs
    Bonnet, Édouard ; Cabello, Sergio ; Mulzer, Wolfgang
    Let ▫$G$▫ be an intersection graph of ▫$n$▫ geometric objects in the plane. We show that a maximum matching in ▫$G$▫ can be found in ▫$O(\rho^{3\omega/2}n^{\omega/2})$▫ time with high probability, ... where ▫$\rho$▫ is the density of the geometric objects and ▫$\omega>2$▫ is a constant such that ▫$n \times n$▫ matrices can be multiplied in ▫$O(n^\omega)$▫ time. The same result holds for any subgraph of ▫$G$▫, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in ▫$O(n^{\omega/2})$▫ time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in ▫$[1, \Psi]$▫ can be found in ▫$O(\Psi^6\log^{11} n + \Psi^{12 \omega} n^{\omega/2})$▫ time with high probability.
    Vir: Discrete & computational geometry. - ISSN 0179-5376 (Vol. 70, iss. 3, Oct. 2023, str. 550-579)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 163998979

    Povezava(-e):

    https://link.springer.com/article/10.1007/s00454-023-00564-3
    Repozitorij Univerze v Ljubljani – RUL
    DiRROS - Digitalni repozitorij raziskovalnih organizacij Slovenije
    DOI

vir: Discrete & computational geometry. - ISSN 0179-5376 (Vol. 70, iss. 3, Oct. 2023, str. 550-579)
loading ...
loading ...
loading ...

Vnos na polico