Optymalny algorytm znajdowania obwodu rzadkiego wykresu?

Zastanawiam się, jak znaleźć obwód rzadkiego niekierowanego 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 osiągnąć od pierwszej części. Jednak mogę być na niewłaściwym torze. Każdy algorytm asymptotycznie lepszy niż Θ ( | V | 2 ) (tj. O ( | V | 2 ) ) jest mile widziany.$O(|V|)$$\Theta(|V|^2)$$o(|V|^2)$

$O(n^2)$$g$$g$$g+1$$1$

$O($$n^{2.38}, m^{1.41})$$n$$m$$O(n^{2.38})$$O(mn)$$o(n^2)$$m=O(n)$

$2$$n^{1+1/k}$$2k$. Im gęstszy jest wykres, tym łatwiej jest znaleźć dobre przybliżenie obwodu. Gdy wykres jest bardzo rzadki, obwód może być zasadniczo dowolny.

Znalezienie obwodu wykresu płaskiego ma ciekawą historię. Zobacz ten artykuł autorstwa Changa i Lu, aby uzyskać liniowy algorytm czasu i historię ulepszeń.

Nie ma ogólnej techniki znajdowania obwodu jakiegokolwiek rzadkiego wykresu. Często musimy szukać powiązanych specjalnych rozkładów lub osadzeń, aby osiągnąć lepsze granice. Jeśli wykres jest „możliwy do udowodnienia” rzadki, często wiąże się z nim ładna struktura. Na przykład ograniczone wykresy szerokości są rzadkie i mają związany z nimi rozkład drzewa.

$o(n^2)$