| Naslov: | Maximum matchings in geometric intersection graphs |
|---|
| Avtorji: | ID Bonnet, Édouard (Avtor)
ID Cabello, Sergio (Avtor)
ID Mulzer, Wolfgang (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (576,69 KB)
MD5: CFA5DBABF17761B11ACC25F11DBAF784
 URL - Izvorni URL, za dostop obiščite https://link.springer.com/article/10.1007/s00454-023-00564-3
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | computational geometry, geometric intersection graphs, disk graphs, unit-disk graphs, matchings |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.10.2023 |
|---|
| Leto izida: | 2023 |
|---|
| Št. strani: | str. 550-579 |
|---|
| Številčenje: | Vol. 70, iss. 3 |
|---|
| PID: | 20.500.12556/DiRROS-18632  |
|---|
| UDK: | 004.42:515.17 |
|---|
| ISSN pri članku: | 0179-5376 |
|---|
| DOI: | 10.1007/s00454-023-00564-3 |
|---|
| COBISS.SI-ID: | 163998979 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 08.04.2024 |
|---|
| Število ogledov: | 1021 |
|---|
| Število prenosov: | 499 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
