Подсчет количества различных с-т разрезов в ориентированном графе - PullRequest
2 голосов
/ 01 декабря 2011

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

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

1 Ответ

2 голосов
/ 21 декабря 2011

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

...