Optymalny algorytm do znalezienia obwodu rzadkiego wykresu?

Zastanawiam się, jak znaleźć obwód rzadkiego nieukierunkowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową. $|E|=O(|V|)$

Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy w , to znajdę obwód poprzez jakąś indukcję, którą można uzyskać od pierwszej części. Ale mogę być na niewłaściwym torze. Każdy algorytm asymptotycznie lepszy niż (tj. ) jest mile widziany. $O(|V|)$ $\Theta(|V|^2)$ $o(|V|^2)$

Jest to prawdopodobnie wciąż otwarty problem i być może lepiej nadaje się do cstheory.

Aryabhata

Ale należałoby zapytać na cstheory, czy jest to otwarty problem.

JeffE

@ Suresh, nie mogę myśleć lepiej niż

dla BFS. Również jeśli jest to odpowiednie dla CStheory, zapytam o to jutro.

Ω (n^{2})

$\Omega(n^2)$

Uwaga: to pytanie zostało przeniesione do cstheory. Głosowanie na zakończenie.

Suresh

@Suresh: Zamiast zamykać, powinniśmy po prostu dodać tutaj odpowiedź z linkiem do odpowiedzi tam, mówiąc, że odpowiedź została udzielona w cstheory. Poza tym, jak byśmy to zamknęli? Poza tematem? (Dodałem odpowiedź CW).

Aryabhata

Odpowiedzi:

Zobacz Optymalny algorytm znajdowania obwodu rzadkiego wykresu z cstheory.SE, który ma zaakceptowaną odpowiedź.

Aryabhata
źródło

Myślę, że odpowiedź w CSTheory nie jest kompletna, czekam na więcej referencji, więc nie oznaczyłem jej jeszcze jako odpowiedzi. Ale tutaj możesz zdecydować o zamknięciu tego, ale nie zamierzam go usuwać, ponieważ uważam, że dobrze jest mieć historię tego problemu w CS. PS: Wiem, że Shiva jest doskonała w pokrewnych dziedzinach, ale myślę, że lepiej pozostawić to otwarte, może ktoś inny ma lepsze referencje.

@SaeedAmiri: Nie zawsze możesz znaleźć referencję. Możliwe, że nikt wcześniej nie rozważał tego problemu ani nie odnotował go wyraźnie na otwartej liście problemów. Zawsze możesz jednak pozostawić swoje pytanie nieoznaczone. btw, jestem przeciwny zamknięciu go tutaj. To jest całkowicie poprawne pytanie dla tej witryny, a zamknięcie go może dać złe wrażenie przyszłym pytającym.

Aryabhata

spójrz teraz na pytanie cstheory.

Suresh

Zobacz także Wykład na temat cyklu na wykresie .

Pål GD