Перечисление всех минимальных направленных циклов ориентированного графа
У меня есть ориентированный граф, и моя проблема состоит в том, чтобы перечислить всеминимальный (циклы, которые нельзя построить как объединение других циклов) направленные циклы этого графа. Это отличается от того, что выводит алгоритм Тарьяна. Например, для ориентированного графа вэта страница википедииЯ хотел бы получить c <-> d и d <-> h как два отдельных направленных цикла.
Я не знаю, является ли эта проблема полиномиальной или нет. Я перебрал статью «Перечисление минимальных дикутов и сильно связанных подграфов», в которой, похоже, делается вывод о том, что эта проблема является возрастающим полиномом (я не знаю, что это значит), но я не могу извлечь алгоритм для этой статьи. Я также не уверен, что минимальный сильно связанный компонент эквивалентен минимальному циклу, как я его определяю.
Кто-нибудь знает ответ на эту проблему?
Заранее спасибо!!!