Граница времени выполнения

Теперь посмотрим, насколько быстро можно вычислить максимальное паросоче- тание в G. Пусть n = X = |Y|, а m — количество ребер в G. Будем предполагать, что существует хотя бы одно ребро, инцидентное каждому узлу из исходной задачи — а следовательно, m > n/2.
Во времени вычисления максимального паросочетания доминирующим фактором является время вычисления целочисленного макси- мального потока в G\ так как преобразование его в паросочетание в G выполняется просто. Для этой задачи потока имеем C=∑,
<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Граница времени выполнения:

  1. Управление временем «Нам некогда делать это как следует - у нас хватает времени лишь на то, чтобы потом все переделывать».
  2. Линия времени "во времени"
  3. Я-ГРАНИЦА
  4. Границы эго
  5. Границы
  6. § 7. Смежные права и их границы
  7. Часть I. Границы Ума
  8. § 5. Границы исключительных авторских прав
  9. Царство без границ
  10. Нарушение границы
  11. Нарушение границы