arXiv preprint ·
Estimating the number of nodes and paths in a DAG by following a random path
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Four-Coloring Planar Graphs in Linear Time
A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs
From Trees to Binary Trees: Approximation Algorithms and a PTAS
Local-to-Global Theorems Based on Cones with Applications to Graph Coloring
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.