Efficient many-to-Many point matching in one dimension

DOI10.1007/S00373-007-0714-3MaRDI QIDQ2373930zbMATH OpenOpenAlexWikidataFDO

Authors Justin Colannino, Mirela Damian, Stefan Langerman, Diane L. Souvaine, Godfried Toussaint, Ferran Hurtado, Henk Meijer, Suneeta Ramaswami

Publication date 19 July 2007

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-007-0714-3

zbMATH Keywords

complexitymatching problemminimum-cost

Mathematics Subject Classification ID

Operations research and management science (90B99)

Recommendations

• An O(n^2) algorithm for the limited-capacity many-to-many point matching in one dimension
• Bipartite graph matching for points on a line or a circle
• Minimum many-to-many matchings for computing the distance between two sequences
• Fast Matching Algorithms for Points on a Polygon
• Geometry Helps in Matching

Cites work

• An algorithm for computing the restriction s|caffold assignment problem in computational biology
• An efficient algorithm for minimum-weight bibranching
• Distance measures for point sets and their computation
• Fast Matching Algorithms for Points on a Polygon
• Geometry helps in bottleneck matching and related problems
• Geometry Helps in Matching
• scientific article; zbMATH DE number 6118218 (Why is no real title available?)
• scientific article; zbMATH DE number 2090782 (Why is no real title available?)
• Min-max Relations for Directed Graphs
• On some techniques useful for solution of transportation network problems
• The Geometry of Musical Rhythm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Two special cases of the assignment problem

Cited in

(11)

• A fast algorithm for maximal propensity score matching
• Comment: Matching methods for observational studies derived from large administrative databases
• Faster retrieval with a two-pass dynamic-time-warping lower bound
• Geometric planar networks on bichromatic collinear points
• An O(n^2) algorithm for the limited-capacity many-to-many point matching in one dimension
• Bipartite graph matching for points on a line or a circle
• Minimum many-to-many matchings for computing the distance between two sequences
• Evaluating individualized treatment effect predictions: a model-based perspective on discrimination and calibration assessment
• An o(n n)-time approximation scheme for geometric many-to-many matching
• Constrained many-to-many point matching in two dimensions
• Computational geometric aspects of rhythm, melody, and voice-leading

This page was built for publication: Efficient many-to-Many point matching in one dimension

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