J. Delon, J. Salomon, A. Sobolevski, “Minimum-weight perfect matching for non-intrinsic distances on the line”, Zap. Nauchn. Sem. POMI, 2011, Volume 390,Pages <nobr>52

This article is cited in 2 papers

Minimum-weight perfect matching for non-intrinsic distances on the line

J. Delon^a, J. Salomon^b, A. Sobolevski^cd

^a LTCI CNRS, TELECOM ParisTech, Paris, France
^b CEREMADE, Université Paris-Dauphine, Paris, France
^c Institute for Information Transmission Problems (Kharkevich Institute), Moscow, Russia
^d Laboratoire J.-V. Poncelet (UMI 2615 CNRS), Moscow, Russia

Abstract: We consider a minimum-weight perfect matching problem on the line and establish a “bottom-up” recursion relation for weights of partial minimum-weight matchings.

Key words and phrases: minimum-weight perfect matching, recursion, bipartite matching, concavity.

UDC: 519.854.2

Received: 15.09.2011

Language: English