Maximum Matchings in Geometric Intersection Graphs

Édouard Bonnet, Sergio Cabello & Wolfgang Mulzer
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 data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.