У меня есть ориентированный граф, и моя проблема состоит в том, чтобы перечислить всеминимальный (циклы, которые нельзя построить как объединение других циклов) направленные циклы этого графа. Это отличается от того, что выводит алгоритм Тарьяна. Например, для ориентированного графа вэта страница википедииЯ хотел бы получить с <-> д и д <-> ч как два отдельных направленных цикла.

Я нет, если эта проблема является полиномиальной или нет. Я перебрал бумагуПеречисление минимальных дикутов и сильно связанных подграфов » кажется, приходит к выводу, что эта проблема является инкрементным полиномом (я неЯ не знаю, что это значит), но я не могу извлечь алгоритм для этой статьи. Я также не уверен, что минимальный сильно связанный компонент эквивалентен минимальному циклу, как я его определяю.

Кто-нибудь знает ответ на эту проблему?

Заранее спасибо!!!