Jakie ograniczenia można nałożyć na liczenie osiągalnych węzłów w dag?

Podany jest sztylet. Chcesz oznaczyć każdy węzeł liczbą dostępnych węzłów. jest trywialną górną granicą; Ω ( V + E ) to dolna granica (tak myślę). Czy istnieje lepszy algorytm? Czy istnieje powód, by sądzić, że dolną granicę można poprawić (powiązane: co dokładnie wiadomo o dolnych granicach w przypadku przechodzenia przejściowego)?$O(V(V+E))$$\Omega(V+E)$

Motywacja: Musiałem to zrobić kilka razy, przedstawiając fol formuły jako sztylety.

Edycja: Pamiętaj, że po prostu liczy ścieżki , nieosiągalne węzły . (Dodałem to, ponieważ najwyraźniej wiele osób uważało, że to proste rozwiązanie zadziałałoby dzięki głosom, które widziałem w usuniętej odpowiedzi). W rzeczywistości problem ten pojawia się właśnie wtedy, gdy chcesz zrobić coś interesującego z „wspólnymi” częściami, węzłami dostępnymi przez więcej niż jedna ścieżka. Mówię też dag, ponieważ jeśli zostaną rozwiązane, rozwiązywanie digrafów jest łatwe.$c_x=1+\sum_{x\to y}c_y$

Przejściowe zamknięcie ukierunkowanego wykresu o krawędziach i n wierzchołkach można obliczyć nieco szybciej niż czas O ( m n ) , ale niewiele. O ( n 2 + m n / log n ) Algorytm czas jest wymieniony w przypisie 2005 zwitki papieru Chana na APSP (wersja czasopisma w Algorithmica 2008). Niewielka poprawa do O ( n 2 + m n log ( n 2 / m ) / log 2$m$$n$$O(mn)$$O(n^2 + mn/\log n)$ można znaleźć w artykule ICALP'08 „Nowe podejście kombinatoryczne dla problemów z rzadkimi grafami” Blellocha, Vassilevskiej i Williamsa. To powiedziawszy, nie wiem, czy liczenie potomków jest łatwiejsze niż ich znalezienie$O(n^2 + mn \log(n^2/m)/\log^2 n)$

Myślę, że możesz użyć mnożenia macierzy, aby obliczyć przechodnie zamknięcie DAG, a następnie użyć liczby sąsiadów jako pożądanej liczby. Nie jestem ekspertem w dziedzinie literatury, ale myślę, że można obliczyć zamknięcie przechodnie w tym samym czasie, co mnożenie macierzy, tj. czas: http://www.computer.org/portal/web/csdl/doi/10.1109/ ACSSC.1995.540810 .$n^{\omega}$

Może nie jest to przydatne w twoim kontekście, ale możesz uzyskać przybliżenie za pomocą Synopsis Diffusion (http://www.cs.cmu.edu/~sknath/sd.htm). Myślę, że to czyni O (V + E). Symulowanie dyfuzji streszczenia na uniprocesorze wydaje mi się być O (V + E), (najpierw musisz wykonać sortowanie topologiczne, które jest również O (V + E)).