Euclidean maximum matchings in the plane -- local to global
DOI10.1007/s00453-024-01279-4MaRDI QIDQ6670815
Ahmad Biniaz, Anil Maheshwari, Michiel Smid
Publication date: 24 January 2025
Published in: Algorithmica (Search for Journal in Brave)
maximum matchingglobal maximumlocal maximumpairwise crossing matchingpairwise intersecting disksplanar points
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Long non-crossing configurations in the plane
- Partitioning heuristics for two geometric maximization problems
- On the Euclidean assignment problem
- Multicommodity flows in planar graphs
- Über Mengen konvexer Körper mit gemeinschaftlichen Punkten.
- Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten.
- A linear-time algorithm for edge-disjoint paths in planar graphs
- Matching points with disks with a common intersection
- On maximum-sum matchings of points
- On Local Search for Weighted k-Set Packing
- Linear-Time Approximation for Maximum Weight Matching
- A survey of heuristics for the weighted matching problem
- An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Data Structures for Weighted Matching and Extensions to b -matching and f -factors
- Paths, Trees, and Flowers
- Maximum matching and a polyhedron with 0,1-vertices
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
- Maximum plane trees in multipartite geometric graphs
- Stabbing pairwise intersecting disks by four points
- Intersecting ellipses induced by a max-sum matching
This page was built for publication: Euclidean maximum matchings in the plane -- local to global
