Efficient many-to-many point matching in one dimension

被引：15

作者：

Colannino, Justin ^{[1
]}

Damian, Mirela

Hurtado, Ferran

Langerman, Stefan

Meijer, Henk

Ramaswami, Suneeta

Souvaine, Diane

Toussaint, Godfried

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada

[2] Villanova Univ, Dept Comp Sci, Villanova, PA 19085 USA

[3] Univ Politecn Catalunya, Dept Matemat Aplicada 2, Barcelona, Spain

[4] Univ Libre Bruxelles, Dept Informat, Chercheur Qualifie FNRS, Brussels, Belgium

[5] Rutgers State Univ, Dept Comp Sci, Camden, NJ 08102 USA

[6] Queens Univ, Sch Computing, Kingston, ON, Canada

[7] Tufts Univ, Dept Comp Sci, Medford, MA 02155 USA

[8] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada

[9] McGill Univ, Schulich Sch Mus, CIRMMT, Montreal, PQ, Canada

来源：

GRAPHS AND COMBINATORICS | 2007年 / 23卷 / Suppl 1期

关键词：

D O I：

10.1007/s00373-007-0714-3

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 is an element of S to t is an element of 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(n(2)) for the same problem.

引用

页码：169 / 178

页数：10

共 22 条

[1] The restriction scaffold problem [J].