Digitalni repozitorij raziskovalnih organizacij Slovenije

Izpis gradiva
A+ | A- | Pomoč | SLO | ENG

Naslov:Maximum matchings in geometric intersection graphs
Avtorji:ID Bonnet, Édouard (Avtor)
ID Cabello, Sergio (Avtor)
ID Mulzer, Wolfgang (Avtor)
Datoteke:.pdf PDF - Predstavitvena datoteka, prenos (576,69 KB)
MD5: CFA5DBABF17761B11ACC25F11DBAF784
 
URL 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:Logo 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 Novo okno
UDK:004.42:515.17
ISSN pri članku:0179-5376
DOI:10.1007/s00454-023-00564-3 Novo okno
COBISS.SI-ID:163998979 Novo okno
Opomba:
Datum objave v DiRROS:08.04.2024
Število ogledov:493
Število prenosov:236
Metapodatki:XML DC-XML DC-RDF
:
Kopiraj citat
  
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Discrete & computational geometry
Skrajšan naslov:Discrete comput. geom.
Založnik:Springer
ISSN:0179-5376
COBISS.SI-ID:25342208 Novo okno

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:P1-0297

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:J1-9109

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:J1-8130

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:J1-8155

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:J1-1693

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:J1-2452

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:N1-0218

Financer:EC - European Commission
Številka projekta:StG 757609

Licence

Licenca:CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by/4.0/deed.sl
Opis:To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Nazaj