Я пытаюсь найти количество различных s-t срезов в ориентированном невзвешенном графике. В статье Перечисление в графиках с. 45 Я нашел хороший способ перечислить эти сокращения (раздел 7.3). Есть ли более быстрый или более простой алгоритм, который я могу использовать, если меня интересует только количество таких сокращений и мне нет нужды перечислять его?
Я использую следующее определение s-t cut. У нас есть ориентированный граф, в котором две вершины помечены S и T . Cut - это минимальный набор ребер графа, такой, что, удаляя эти ребра, больше не будет существовать путь от вершины S до вершины T .