20.500.12556/RUL-155610 Maximum matchings in geometric intersection graphs 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. computational geometry geometric intersection graphs disk graphs unit-disk graphs matchings true false true Angleški jezik Angleški jezik Članek v reviji 2024-04-08 12:06:15 2024-04-08 12:06:17 2024-04-09 03:46:02 0000-00-00 00:00:00 2023 0 0 Str. 550-579 iss. 3 Vol. 70 Oct. 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2023-10-01 004.42:515.17 0179-5376 10.1007/s00454-023-00564-3 163998979 s00454-023-00564-3-1.pdf s00454-023-00564-3-1.pdf 1 2AE24C477662826A929643D03286407E 5b9013451bd523edcdf809c3b7597c04a11203a466296ff81d0561b83062ed0e 2ab4dcea-f591-11ee-937a-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=182587 https://link.springer.com/article/10.1007/s00454-023-00564-3 1 a4fea7cf-f58f-11ee-937a-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=182586 Fakulteta za matematiko in fiziko 0 0 0