Подсчет количества различных срезов в ориентированном графе

Question

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

Я использую следующее определение st-cut. У нас есть ориентированный граф, где две вершины помечены как S и T. Cut - это минимальный набор ребер графа, такой, что, удаляя эти ребра, больше не будет существовать путь от вершины S к вершине T.

Answer 1

CSteory.StackExchange был тем местом! На мой вопрос ответилиотрицательно.