Linear transformation distance for bichromatic matchings

DOI10.1145/2582112.2582151MaRDI QIDQ4635538zbMATH OpenOpenAlexFDO

Authors Oswin Aichholzer, Alexander Pilz, Birgit Vogtenhuber, Luis Barba, T. Hackl

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2582112.2582151

zbMATH Keywords

bichromatic point setcompatible matchingsperfect matchingsreconfiguration problemtransformation graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Linear transformation distance for bichromatic matchings
• scientific article; zbMATH DE number 6381629
• Bicompletions of distance matrices
• Distance matching extension in cubic bipartite graphs
• Linear time algorithms for exact distance transform
• Partial-matching RMS distance under translation: combinatorics and algorithms
• Minimum-weight perfect matching for nonintrinsic distances on the line
• Deterministic, near-linear 𝜀 -approximation algorithm for geometric bipartite matching
• Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms
• Bipartite matching with linear edge weights

Cited in

(4)

• Linear transformation distance for bichromatic matchings
• Disjoint compatibility graph of non-crossing matchings of points in convex position
• Bichromatic compatible matchings
• Bichromatic compatible matchings

This page was built for publication: Linear transformation distance for bichromatic matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635538)