The transitive closure of a random digraph
From MaRDI portal
Publication:3197352
DOI10.1002/rsa.3240010106zbMath0712.68076OpenAlexW2109767783MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items
The critical window in random digraphs, Birth of a Strongly Connected Giant in an Inhomogeneous Random Digraph, An efficient transitive closure algorithm for cyclic digraphs, The bunkbed conjecture on the complete graph, Phase transition phenomena in random discrete structures, Unnamed Item, The scaling window for a random graph with a given degree sequence, How does the core sit inside the mantle?, Phase transitions in dynamical random graphs, The Evolution of Random Subgraphs of the Cube, Random Deterministic Automata, Mean-field conditions for percolation on finite graphs, The giant component of the directed configuration model revisited, Large deviations of the greedy independent set algorithm on sparse random graphs, A scaling limit for the length of the longest cycle in a sparse random digraph, Transitive closure in a polluted environment, The scaling limit of a critical random directed graph, Locality of random digraphs on expanders, The birth of the strong components, Exact enumeration of satisfiable 2-SAT formulae, The diameter of the directed configuration model, On Random Betweenness Constraints, Improved baselines for causal structure learning on interventional data, Average case analysis of fully dynamic connectivity for directed graphs, Generating functions of some families of directed uniform hypergraphs, Functional integration of ecological networks through pathway proliferation, Phase transitions in graphs on orientable surfaces, A remark on random 2-SAT, The scaling window of the 2-SAT transition, Quasispecies dynamics on a network of interacting genotypes and idiotypes: formulation of the model, Component structure of the vacant set induced by a random walk on a random graph, Birth of a giant \((k_{1},k_{2})\)-core in the random digraph, Efficient sampling strategies for relational database operations, Parallel processing of graph reachability in databases, Exploring hypergraphs with martingales, Aggregation models with limited choice and the multiplicative coalescent, The Hausdorff dimension of a class of random self-similar fractal trees, The phase transition in the uniformly grown random graph has infinite order, Information integration from distributed threshold-based interactions, The critical random graph, with martingales, The critical behavior of random digraphs, Critical percolation on random regular graphs, Note on directed proper connection number of a random graph, Survey of Scalings for the Largest Connected Component in Inhomogeneous Random Graphs, On Percolation and the Bunkbed Conjecture, The Largest Component in Subcritical Inhomogeneous Random Graphs, Lengths of Attractors and Transients in Neuronal Networks with Random Connectivities, A power law of order 1/4 for critical mean-field Swendsen-Wang dynamics, Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles, A classification of isomorphism-invariant random digraphs, Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs, Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs, Small Subgraphs in Random Distance Graphs, Random Models for Evaluating Efficient Büchi Universality Checking, On Random Ordering Constraints, Asymptotic normality of the size of the giant component via a random walk, Combinatorial Problems for Horn Clauses, Гигантская компонента в случайных дистанционных графах специального вида, Superspreaders and high variance infectious diseases, BOOLEAN DELAY EQUATIONS ON NETWORKS IN ECONOMICS AND THE GEOSCIENCES, Counting strongly-connected, moderately sparse directed graphs, When does the giant component bring unsatisfiability?, The phase transition in random graphs: A simple proof, Average case analysis of fully dynamic reachability for directed graphs, Heterogeneity and superspreading effect on herd immunity, Asymptotic normality of the size of the giant component in a random hypergraph, Directed cycles and related structures in random graphs. I: Static properties
