pipette
ESEspañol

Estimating the number of nodes and paths in a DAG by following a random path

G\"unter Rote

Preprint

In the authors' words

We investigate a simple method to compute an unbiased estimate of the number of nodes of a directed acyclic graph (DAG) by following a random directed path. This method is due to Leonard Pitt from 1987, and it generalizes a method of D. E. Knuth from the 1960s for estimating the size of a rooted tree. A slight variation makes it possible to estimate the number of source-sink paths. We extend the algorithm to use many "agents" that walk cooperatively through the graph. This extension unifies and generalizes several methods that have been proposed for approximately counting the nodes of a tree.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 28 pages, 5 figures, 10 tables, 4 appendices