Diameter and stationary distribution of random \(r\)-out digraphs
From MaRDI portal
Publication:785578
DOI10.37236/9485zbMath1445.05093arXiv1504.06840OpenAlexW3081664676MaRDI QIDQ785578
Louigi Addario-Berry, Borja Balle, Guillem Perarnau
Publication date: 7 August 2020
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.06840
Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Random walks on graphs (05C81)
Related Items
Random walk on sparse random digraphs, Mixing time of PageRank surfers on sparse random digraphs, On the meeting of random walks on random DFA, The diameter of the directed configuration model, Rankings in directed configuration models with heavy tailed in-degrees, Stationary distribution and cover time of sparse directed configuration models, Cutoff at the ``entropic time for sparse Markov chains, Mixing time trichotomy in regenerating dynamic digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The state complexity of random DFAs
- Stationary distribution and cover time of random walks on random digraphs
- On the connectivity of random m-orientable graphs and digraphs
- The diameter of random regular graphs
- Limit distributions of certain characteristics of random automaton graphs
- Average case analysis of Moore's state minimization algorithm
- Random real trees
- On the Probability of Being Synchronizable
- Learning a Random DFA from Uniform Strings and State Information
- Random Deterministic Automata
- Learning Finite Automata Using Label Queries
- The minimum consistent DFA problem cannot be approximated within any polynomial
- Markov Chains
- Cryptographic limitations on learning Boolean formulae and finite automata
- Random Geometric Graphs
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- The Diameter of Sparse Random Graphs
- Lower Bounds on Learning Random Structures with Statistical Queries
- Exact learning of random DNF over the uniform distribution
- Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
- Learning Random Log-Depth Decision Trees under Uniform Distribution
- The graph structure of a deterministic automaton chosen at random
- Diameter of the Stochastic Mean-Field Model of Distance
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
