Maximum matchings in geometric intersection graphs

DOI10.1007/s00454-023-00564-3MaRDI QIDQ6050213

Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer

Publication date: 12 October 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

matchingcomputational geometrydisk graphgeometric intersection graphunit-disk graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Cites Work

• The analysis of a nested dissection algorithm
• The complexity of the free space for a robot moving amidst fat obstacles
• Realistic input models for geometric algorithms
• Reduced constants for simple cycle graph separation
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Maximum matchings in planar graphs via Gaussian elimination
• Maximum matchings in general graphs through randomization
• Algorithms for Reporting and Counting Geometric Intersections
• Approximating extent measures of points
• Ray Shooting and Parametric Search
• Adding range restriction capability to dynamic data structures
• Generalized Nested Dissection
• Applications of a Planar Separator Theorem
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Separators for sphere-packings and nearest neighbor graphs
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Algorithms – ESA 2004
• Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
• Geometry helps in bottleneck matching and related problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum matchings in geometric intersection graphs