A linear time algorithm for a matching problem on the circle

DOI10.1016/S0020-0190(98)00048-9zbMath0925.68197OpenAlexW2039935006MaRDI QIDQ1129000

Ursula M. Molter, Carlos A. Cabrelli

Publication date: 13 August 1998

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(98)00048-9

zbMATH Keywords

AlgorithmsComputational complexityMinimal matching

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (2)

Transportation distances on the circle ⋮ Partition into almost straight trails

Cites Work

• Unnamed Item
• Unnamed Item
• Weighted median algorithms for \(L_ 1\) approximation
• Two special cases of the assignment problem
• A linear selection algorithm for sets of elements with weights
• The Kantorovich metric for probability measures on the circle
• A distance metric for multidimensional histograms
• Bipartite graph matching for points on a line or a circle
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $

This page was built for publication: A linear time algorithm for a matching problem on the circle