Optymalny algorytm znajdowania obwodu rzadkiego wykresu?

14

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ż (tj. ) jest mile widziany. $O(|V|)$ $\Theta(|V|^2)$ $o(|V|^2)$

ds.algorithms graph-theory open-problem

— Saeed
źródło

1

Virginia Vassilevska Williams i Ryan Williams mają artykuł pokazujący, że znalezienie obwodu na ogólnych wykresach jest równoważne APSP w pod przekształceniach podrzędnych. Nie wiem, czy relacja dotyczy rzadkich wykresów, ale oznacza to, że przejście podkwadratowe może być trudne. Pozwolę jednemu z nich opublikować szczegóły :)

— Suresh Venkat

kopia na temat informatyki .

— Kaveh

Nie zostawiamy komentarzy na temat wpisów FAQ, jeśli masz sugestię, możesz rozpocząć meta-dyskusję lub opublikować tutaj .

— Kaveh

24

$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.

— dziewice
źródło

5

niesamowite ! Miałem nadzieję, że pojawi się ekspert :)

— Suresh Venkat,

O (m^{1.41})

$O(m^{1.41})$

2

O (m^{1.41})

$O(m^{1.41})$

Istnieje prosty i ogólny algorytm O (nm) oparty na BFS, o którym nie jestem zaskoczony, że nikt nie wspominał: webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/…

— Labo

5

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)$

— Shiva Kintali
źródło

Dzięki planarny papier wydaje się interesujący.

— Saeed