Size-Estimation Framework with Applications to Transitive Closure and Reachability

@article{citeulike:1996182, abstract = {Computing the transitive closure in directed graphs is a fundamental graph problem. We consider the more restricted problem of computing the number of nodes reachable from every node and the size of the transitive closure. The fastest known transitive closure algorithms run inO(minmn, n2.38) time, wherenis the number of nodes andmthe number of edges in the graph. We present anO(m) time randomized (Monte Carlo) algorithm that estimates, with small relative error, the sizes of all reachability sets and the transitive closure. Another ramification of our estimation scheme is a O(m) time algorithm for estimating sizes of neighborhoods in directed graphs with nonnegative edge lengths. Our size-estimation algorithms are much faster than performing the respective explicit computations.}, author = {Cohen, Edith }, citeulike-article-id = {1996182}, doi = {http://dx.doi.org/10.1006/jcss.1997.1534}, journal = {Journal of Computer and System Sciences}, keywords = {algorithms, monte-carlo, randomized-algorithms, transitive-closure}, month = {December}, number = {3}, pages = {441--453}, posted-at = {2007-11-27 19:31:32}, priority = {0}, title = {Size-Estimation Framework with Applications to Transitive Closure and Reachability}, url = {http://dx.doi.org/10.1006/jcss.1997.1534}, volume = {55}, year = {1997} }

TY - JOUR ID - citeulike:1996182 L3 - citeulike-article-id:1996182 TI - Size-Estimation Framework with Applications to Transitive Closure and Reachability JF - Journal of Computer and System Sciences VL - 55 IS - 3 SP - 441 EP - 453 N2 - Computing the transitive closure in directed graphs is a fundamental graph problem. We consider the more restricted problem of computing the number of nodes reachable from every node and the size of the transitive closure. The fastest known transitive closure algorithms run inO(minmn, n2.38) time, wherenis the number of nodes andmthe number of edges in the graph. We present anO(m) time randomized (Monte Carlo) algorithm that estimates, with small relative error, the sizes of all reachability sets and the transitive closure. Another ramification of our estimation scheme is a O(m) time algorithm for estimating sizes of neighborhoods in directed graphs with nonnegative edge lengths. Our size-estimation algorithms are much faster than performing the respective explicit computations. KW - algorithms KW - monte-carlo KW - randomized-algorithms KW - transitive-closure AU - Cohen, Edith PY - 1997/12// UR - http://dx.doi.org/10.1006/jcss.1997.1534 ER -