Cargando…

Maximum Matchings in Geometric Intersection Graphs

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 [Formula: see text] time with high probability, where [Formula: see text] is the density of the geometric objects and [Formula: see text] is a constant such that [Formula: see tex...

Descripción completa

Detalles Bibliográficos
Autores principales: Bonnet, Édouard, Cabello, Sergio, Mulzer, Wolfgang
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10550895/
https://www.ncbi.nlm.nih.gov/pubmed/37808959
http://dx.doi.org/10.1007/s00454-023-00564-3