J. Delon, J. Salomon, A. Sobolevski, “Minimum-weight perfect matching for non-intrinsic distances on the line”, Зап. научн. сем. ПОМИ, 2011, том 390,страницы 52

Эта публикация цитируется в 2 статьях

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

Аннотация: Рассмотрена задача о совершенном паросочетании минимального веса на вещественной прямой и выведено рекурсивное соотношение, позволяющее вычислить веса всех возможных частичных паросочетаний “снизу вверх”. Библ. – 11 назв.

Ключевые слова: совершенное спаривание минимального веса, рекурсия, спаривание в двудольном графе, вогнутость.

УДК: 519.854.2

Поступило: 15.09.2011

Язык публикации: английский