Maximum Matchings in Geometric Intersection Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929331943505920 |
|---|---|
| author | Bonnet, Édouard Cabello, Sergio Mulzer, Wolfgang |
| author_facet | Bonnet, Édouard Cabello, Sergio Mulzer, Wolfgang |
| contents | 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(ρ^{3ω/2}n^{ω/2})$ time with high probability, where $ρ$ is the density of the geometric objects and $ω>2$ is a constant such that $n \times n$ matrices can be multiplied in $O(n^ω)$ 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^{ω/2})$ time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in $[1, Ψ]$ can be found in $O(Ψ^6\log^{11} n + Ψ^{12 ω} n^{ω/2})$ time with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1910_02123 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Maximum Matchings in Geometric Intersection Graphs Bonnet, Édouard Cabello, Sergio Mulzer, Wolfgang Computational Geometry Data Structures and Algorithms 68Q25 F.2.2 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(ρ^{3ω/2}n^{ω/2})$ time with high probability, where $ρ$ is the density of the geometric objects and $ω>2$ is a constant such that $n \times n$ matrices can be multiplied in $O(n^ω)$ 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^{ω/2})$ time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in $[1, Ψ]$ can be found in $O(Ψ^6\log^{11} n + Ψ^{12 ω} n^{ω/2})$ time with high probability. |
| title | Maximum Matchings in Geometric Intersection Graphs |
| topic | Computational Geometry Data Structures and Algorithms 68Q25 F.2.2 |
| url | https://arxiv.org/abs/1910.02123 |