"Записки научных семинаров ПОМИ"
Том 390, стр. 52-68
Совершенные паросочетания минимального веса для метрик на числовой прямой, не являющихся внутренними
Ж. Делон, Ж. Саломон, А. Соболевский
TCI CNRS TELECOM ParisTech, 46 rue Barrault,
75634 Paris, France
CEREMADE,
Universit\'e Paris-Dauphine,
Place du Marechal Lattre de Tassigny,
75775 Paris, France
Institute for Information Transmission Problems (Kharkevich
Institute),
19 B. Karetny per.,
Moscow 127994, Russia
Laboratoire J.-V. Poncelet (UMI 2615 CNRS),
11 B. Vlassievski per.,
Moscow 119002, Russia
sobolevski@iitp.ru
- Аннотация:
Рассмотрена задача о совершенном паросочетании минимального
веса на вещественной прямой и выведено рекурсивное соотношение,
позволяющее вычислить веса всех возможных частичных паросочетаний
``снизу вверх''.
Библ. -- 17 назв.
- Ключевые слова: совершенное спаривание минимального веса, рекурсия,
спаривание в двудольном графе, вогнутость
[minimum-weight perfect matching, recursion,
bipartite matching, concavity]
Полный текст(.pdf)