Ograniczasz wykorzystanie miejsca przez łączność st za pomocą wielu przebiegów?

20

Załóżmy, że wykres z wierzchołkami jest przedstawiony jako strumień krawędzi, ale nad strumieniem dozwolonych jest wiele przejść. $G$ $n$ $m$

Monika Rauch Henzinger, Prabhakar Raghavan i Sridar Rajagopalan zauważyli, że przestrzeń jest niezbędna do ustalenia, czy istnieje ścieżka między dwoma podanymi wierzchołkami w , jeśli dopuszcza się przejść przez dane. (Zobacz także wersję raportu technicznego .) Nie zapewniają one jednak algorytmu umożliwiającego osiągnięcie tego ograniczenia. Zakładam, że optymalny algorytm faktycznie wziąłby $\Omega(n/k)$ $G$ $k$ przestrzeń w realistycznym modelu obliczeniowym, ponieważ trzeba rozróżnić różnych wierzchołków, jeśli nie można indeksować pamięci za pomocą wskaźników o stałym rozmiarze. $O((n\, \log\, n)/k)$ $n$

Jak można zdecydować o połączeniu grafu za pomocą przejść za pomocą $k$ spacja? $O((n\, \log\, n)/k)$

Jeśli dozwolone jest tylko jedno przejście, dane wejściowe mogą być przechowywane jako partycja zestawu wierzchołków, łącząc zestawy, jeśli krawędź jest widoczna między wierzchołkami w dwóch różnych zestawach. Wymaga to najwyżej co najwyżej przestrzeń. Moje pytanie dotyczy : jak można użyć większej liczby przejść, aby zmniejszyć wymaganą przestrzeń? $O(n\, \log\, n)$ $k > 1$

(Aby uniknąć trywialności, jest parametrem, którego a priori nie można ograniczyć stałą, a granice przestrzeni są wyrażeniami obejmującymi funkcje zarówno jak i .) $k$ $n$ $k$

Aktualizacja: nawet dla naprawdę przydatny byłby sposób przechowywania tylko wierzchołków. Czy jest tam rzeczywiście silniejszy dolny dla pewnej stałej , niezależnie od ? $k=2$ $n/2$ $cn$ $c$ $k$

— András Salamon
źródło

Jak niezależnie od

? Jeśli może być bardzo duży, to łączność st można rozwiązać w przestrzeni

, więc istnieje szansa na algorytm, ale jak pokazuje azotlichid, prawdopodobnie nie w

.

k

$k$

O (\log^{2} n)

$O(\log^2 n)$

O (n \log n / k)

$O(n\log n /k)$

— domotorp,

Zauważ, że eliminacja przepustek Guha i McGregor dla algorytmów losowych działa w przeciwnym kierunku, wykorzystując więcej miejsca, aby umożliwić mniej przebiegów (choć dodatkowa przestrzeń jest duża, jeśli pożądany błąd jest niewielki). To pytanie dotyczy tego, czy przy użyciu większej liczby przebiegów można zmniejszyć wykorzystanie miejsca.

— András Salamon

8

Od dawna otwartym problemem jest znalezienie algorytmu łączności st, który działa jednocześnie w przestrzeni subliniowej i czasie wielomianowym, co jest łatwiejszym zadaniem niż to, do czego dążysz. Takie algorytmy są znane dla wersji bezkierunkowej , ale nawet one wymagają dużego czasu wielomianowego (zamiast czasu O (km), co wynikałoby z algorytmu k-pass). Zobacz w szczególności odniesienie do pracy Tompy na temat tego, dlaczego skierowana sprawa wydaje się trudna.

— Noam
źródło

1

M. Tompa, Dwa znane algorytmy zamykania przechodniego, które nie dopuszczają czasu wielomianowego, implementacje przestrzeni podliniowej, SIAM J. Comput. 11 (1), 130–137. dx.doi.org/10.1137/0211010

— András Salamon

Ten artykuł daje „algorytm dla st-connectivity, który działa jednocześnie

$\hspace{1.71 in}$ sub-liniowej przestrzeni i czasie wielomianowym.”

4

$k = \Theta(n)$ $O(\log n)$ $O(nm)$

— zotachidil
źródło

3

$k$

— Chad Brewbaker
źródło

Dzięki za wskaźnik, to ciekawy papier. Procesory mają wspólny dostęp do struktury danych, która jest co najmniej tak duża jak wykres, więc nie pomaga to zmniejszyć wykorzystania miejsca. Byłoby naprawdę interesujące, gdyby istniał sposób na zmniejszenie wykorzystania miejsca poprzez wykorzystanie liczby rund, a także liczby procesorów.

— András Salamon,

2

Jeszcze jedna odpowiedź: jest kilka artykułów na temat algorytmów w stylu mapreduce działających na dużych wykresach. Celem jest uzyskanie przestrzeni o (m) na maszynę dla gęstych wykresów, ale zwykle potrzeba przestrzeni O (n) na maszynę.

teorii.stanford.edu/~sergei/papers/soda10-mrc.pdf http://theory.stanford.edu/~sergei/papers/spaa11-matchings.pdf

— Martin Pál
źródło

1

$O(n\log n/ k)$ $k$ $n/k$ $st$ $n/k$ $n/k$ $st$

— domotorp
źródło