The transitive closure of a random digraph
From MaRDI portal
Publication:3197352
DOI10.1002/rsa.3240010106zbMath0712.68076MaRDI QIDQ3197352
Publication date: 1990
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240010106
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
The phase transition in the uniformly grown random graph has infinite order, Survey of Scalings for the Largest Connected Component in Inhomogeneous Random Graphs, The Hausdorff dimension of a class of random self-similar fractal trees, Efficient sampling strategies for relational database operations, Parallel processing of graph reachability in databases, Asymptotic normality of the size of the giant component via a random walk, Phase transitions in dynamical random graphs, The critical random graph, with martingales, When does the giant component bring unsatisfiability?, An efficient transitive closure algorithm for cyclic digraphs, Phase transition phenomena in random discrete structures, Directed cycles and related structures in random graphs. I: Static properties, A remark on random 2-SAT, Unnamed Item, Mean-field conditions for percolation on finite graphs, The scaling window of the 2-SAT transition, The critical behavior of random digraphs, Critical percolation on random regular graphs, On Percolation and the Bunkbed Conjecture, The Largest Component in Subcritical Inhomogeneous Random Graphs, Average case analysis of fully dynamic reachability for directed graphs, On Random Ordering Constraints, Combinatorial Problems for Horn Clauses, The Evolution of Random Subgraphs of the Cube
