Mam skierowany wykres i moim problemem jest wyliczenie wszystkichminimalny (cykle, które nie mogą być skonstruowane jako połączenie innych cykli) skierowane cykle tego wykresu. Różni się to od wyników algorytmu Tarjan. Na przykład dla ukierunkowanego wykresu wta strona wikipedii, Chciałbym uzyskać c <-> d i d <-> h jako dwa oddzielne ukierunkowane cykle.

Nie wiem, czy ten problem jest wielomianowy czy nie. Przejrzałem artykuł „Wyliczanie minimalnych dicutów i silnie połączonych podgrafów”, który wydaje się prowadzić do wniosku, że ten problem jest przyrostowym wielomianem (nie wiem, co to znaczy), ale nie mogę wyodrębnić algorytmu dla tego artykułu. Nie jestem też pewien, czy minimalny, silnie połączony komponent jest równoważny minimalnemu cyklowi, jaki zdefiniowałem.

Czy ktoś zna odpowiedź na ten problem?

Z góry dziękuję!!!