Quelles limites peut-on imposer au comptage des nœuds accessibles dans un dag?

Donné est un poignard. Vous souhaitez étiqueter chaque nœud en fonction du nombre de nœuds accessibles depuis celui-ci. est une borne supérieure triviale; Ω ( V + E ) est une borne inférieure (je pense). Existe-t-il un meilleur algorithme? Y a-t-il des raisons de croire que la borne inférieure peut être améliorée (lié: que sait-on exactement des bornes inférieures pour la fermeture transitive)?$O(V(V+E))$$\Omega(V+E)$

Motivation: j'ai dû le faire plusieurs fois tout en représentant les formules fol comme des dags.

Edit: Veuillez noter que simplement faire compte les chemins , pas les nœuds accessibles . (J'ai ajouté cela car apparemment, beaucoup de gens pensaient que cette solution simple fonctionnerait par les votes que j'ai vus sur une réponse maintenant supprimée.) En fait, ce problème apparaît précisément lorsque vous voulez faire quelque chose d'intéressant avec des parties `` partagées '', des nœuds accessibles par plus d'un chemin. De plus, je dis dag, car s'ils sont résolus, la résolution des digraphes est facile.$c_x=1+\sum_{x\to y}c_y$

$m$$n$$O(mn)$$O(n^2 + mn/\log n)$$O(n^2 + mn \log(n^2/m)/\log^2 n)$

$n^{\omega}$

Peut-être pas utile dans votre contexte, mais vous pouvez obtenir une approximation en utilisant Synopsis Diffusion (http://www.cs.cmu.edu/~sknath/sd.htm). Je pense que cela en fait O (V + E). La simulation de la diffusion du synopsis sur un monoprocesseur me semble être O (V + E), (vous devez d'abord faire un tri topologique, qui est aussi O (V + E)).