Name
Abstract | ||
|---|---|---|
Let S and T be two sets of points with total cardinality n. The minimum-cost many-to-many matching problem matches each point in S to at least one point in T and each point in T to at least one point in S, such that sum of the matching costs is minimized. Here we examine the special case where both S and T lie on the line and the cost of matching s ∈S to t ∈T is equal to the distance between s and t. In this context, we provide an algorithm that determines a minimum-cost many-to-many matching in O(n log n) time, improving the previous best time complexity of O(n2) for the same problem. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s00373-007-0714-3 | Graphs and Combinatorics |
Keywords | Field | DocType |
previous best time complexity,minimum-cost many-to-many,efficient many-to-many point matching,special case,total cardinality n,n log n,matching cost,time complexity | Discrete mathematics,Point set registration,Combinatorics,Music information retrieval,Cardinality,Time complexity,Many-to-many (data model),Mathematics,Special case | Journal |
Volume | Issue | ISSN |
23 | Supplement-1 | 1435-5914 |
Citations | PageRank | References |
5 | 0.50 | 13 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Justin Colannino | 1 | 19 | 2.23 |
| Mirela Damian | 2 | 212 | 28.18 |
| Ferran Hurtado | 3 | 744 | 86.37 |
| Stefan Langerman | 4 | 831 | 101.66 |
| Henk Meijer | 5 | 753 | 100.25 |
| Suneeta Ramaswami | 6 | 228 | 23.87 |
| Diane L. Souvaine | 7 | 480 | 77.99 |
| Godfried Toussaint | 8 | 1656 | 309.75 |