Вопросы с тегом «matching»

13
Выборка идеального совпадения в случайном порядке

Предположим , у меня есть граф с M ( G ) на (неизвестно) набор совершенных паросочетаний G . Предположим, что это множество не пустое, тогда как трудно выбрать равномерно случайную выборку из M ( G ) ? Что если я в порядке с распределением, близким к равномерному, но не совсем равномерным, то...

11
Как быстро мы можем вычислить размер максимального соответствия в невзвешенном двудольном графе?

Есть ли способ вычислить размер максимального соответствия в невзвешенном двудольном графе более эффективно (например, быстрее), чем вычисление максимального соответствия? Это длинный путь, но часто это интересная проблема, чтобы избежать одноразовых вычислений, подобных этим. мотивация Проблема ,...

10
Пример, где алгоритм Кнута-Морриса-Пратта работает быстрее, чем Бойер-Мур?

Эта страница, посвященная алгоритму Кнута-Мориса-Пратта по сравнению с Бойером-Муром, описывает возможный случай, когда алгоритм Бойера-Мура страдает небольшим пропуском, а KMP может работать лучше. Я ищу хороший пример (текст, шаблон), который может четко продемонстрировать этот...

9
Уменьшить максимальный расход до согласования?

Существует известное и элегантное сокращение от проблемы максимального согласования по двум частям до проблемы максимального потока: мы создаем сеть с исходным узлом , терминальным узлом и одним узлом для каждого сопоставляемого элемента, затем добавляем соответствующие ребра.sssttt Конечно, есть...