• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Minimum—weight perfect matching for nonintrinsic distances on the line

Journal of Mathematical Sciences. 2012. Vol. 181. No. 6. P. 782-791.
Delon J., Salomon J., Sobolevski A.
Рассматривается задача о построении совершенного паросочетания минимального веса в полном графе, вершины которого расположены на числовой прямой, а весами ребер являются расстояния между вершинами в метрике, однородной относительно переносов и, вообще говоря, не являющейся внутренней метрикой для прямой. Выведено рекурсивное соотношение, позволяющее построить такое паросочетание в направлении путем последовательного вычисления оптимальных паросочетаний в подмножествах увеличивающегося объема.