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 (67)
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
This page was built for publication: The transitive closure of a random digraph
