Back to Search
Start Over
Maximum Matchings in Geometric Intersection Graphs.
- Source :
-
Discrete & Computational Geometry . Oct2023, Vol. 70 Issue 3, p550-579. 30p. - Publication Year :
- 2023
-
Abstract
- 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 × 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *INTERSECTION graph theory
*GAUSSIAN elimination
*BIPARTITE graphs
*PLANAR graphs
Subjects
Details
- Language :
- English
- ISSN :
- 01795376
- Volume :
- 70
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete & Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 172779264
- Full Text :
- https://doi.org/10.1007/s00454-023-00564-3