Я хочу очень быстро решить проблему минимального разреза для множества маленьких DAGS (8-12 узлов, 20-60 ребер). Похоже, что лучшее решение — решить максимальный поток и вывести отсечение. Существует довольно много алгоритмов максимального потока с доступными как теоретическими, так и эмпирическими временными сравнениями, но все они предполагают, что интересна производительность, поскольку графики становятся все больше и больше. Также часто упоминается, что время установки для сложных структур данных может быть довольно большим. Итак, учитывая тщательную, оптимизированную реализацию (возможно, в C ++), какой алгоритм оказывается наиболее быстрым для инициализации и запуска на небольших графах? (Мое наивное предположение состоит в том, что Эдмондс-Карп, вероятно, столь же прост с точки зрения структур данных, что превзойдет более сложные алгоритмы, но это только предположение.)
Задача ещё не решена.
Других решений пока нет …