The transitive closure of a random digraph

DOI10.1002/rsa.3240010106zbMath0712.68076MaRDI QIDQ3197352

Richard M. Karp

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

zbMATH Keywords

random digraph; transitive closure algorithm

Mathematics Subject Classification ID

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, On Random Betweenness Constraints, Component structure of the vacant set induced by a random walk on a random graph, 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, BOOLEAN DELAY EQUATIONS ON NETWORKS IN ECONOMICS AND THE GEOSCIENCES, Counting strongly-connected, moderately sparse directed graphs, The phase transition in random graphs: A simple proof, The scaling window for a random graph with a given degree sequence, 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, Asymptotic normality of the size of the giant component in a random hypergraph, Birth of a Strongly Connected Giant in an Inhomogeneous Random Digraph, On Random Ordering Constraints, Combinatorial Problems for Horn Clauses, The Evolution of Random Subgraphs of the Cube