Liczba osiągalnych wierzchołków w DAG dla każdego wierzchołka

11

Niech będzie grafem ukierunkowanym acyklicznie, tak że out-out dowolnego wierzchołka to . Dla każdego wierzchołka możemy policzyć liczbę osiągalnych wierzchołków, po prostu uruchamiając dfs z każdego wierzchołka, a to zajmie czas . Czy istnieje lepszy sposób na rozwiązanie tego problemu? $G(V,E)$ $O(\log{|V|})$ $G$ $O(|V||E|)$

— MikleB
źródło

Powiązane: cstheory.stackexchange.com/q/736/236 cstheory.stackexchange.com/q/553/236

— Radu GRIGore 11.01.11

1

@Radu czy to prosty duplikat? to tak brzmi

— Suresh Venkat

@Suresh, w porównaniu do mojego pytania, ta ma górną granicę stopnia wierzchołka i nie prosi o dolne granice. Są to, moim zdaniem, niewielkie różnice, więc uważam to za duplikat, ale nie czuję się mocno.

— Radu GRIGore

1

ok, więc zostawimy to tak, jak jest.

— Suresh Venkat,

4

Odpowiedź virgiego na moje pytanie oznacza dla tego algorytm

.

O (| V |^{2})

$O(|V|^2)$

— Radu GRIGore

5

Najlepszy dokładny algorytm zadziała w czasie O (min {mn, n ^ 2,38}) przy użyciu szybkiego mnożenia macierzy binarnej. Istnieje jednak algorytm losowy, który działa w czasie O (m + n) i szacuje liczbę osiągalnych węzłów z każdego węzła z niewielkim błędem względnym, zapoznaj się z dokumentem „ Szacunek rozmiaru z aplikacjami do przejściowego zamykania i osiągalności przez Edith Cohen.

— użytkownik22547
źródło

-1

Nie jestem tutaj ekspertem, spróbuję.

1) Ponieważ jest to DAG, powinien mieć wierzchołek zlewu, tzn. Wierzchołek z liczbą zerową 0. Znajdź wierzchołek zlewu powiedz x i dodaj {x} jako osiągalny wierzchołek do Neighbor (x). usuń x i powtarzaj proces, aż wykres stanie się pusty

— Prabu
źródło

Ponieważ out-stopień jest ograniczony, bardziej przydatne byłoby zacząć od źródła?

— András Salamon,

@ andras-salamon: nie, ponieważ nie wiadomo, ile węzłów jest dostępnych ze źródła. Nie robisz tego (zero) dla zlewu.

— Martin B.

O (| V | \cdot | E |)

$O(|V| \cdot |E|)$

x

$x$

O (| V |)

$O(|V|)$

O (| V |)

$O(|V|)$

O (| V |)

$O(|V|)$

O (| V | \cdot | E |)

$O(|V| \cdot |E|)$

-2

(Podobne do rozwiązania Prabu ... ale bardziej szczegółowe)

$N(v)$ $v$ $reach(v)$

$O(|V|+|E|)$
$v$ $reach(v) = \sum_{n\in N(v)} reach(n)$

$|E|$ $O(|V|+|E|)$

— Martin B.
źródło