On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
DOI10.1137/0605049zbMATH Open0558.05026OpenAlexW2085227596MaRDI QIDQ3222867FDOQ3222867
Authors: Amnon Barak, P. Erdős 
Publication date: 1984
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/6a73f0cbff6604de5aabab6a3be04a68df6e36b1
Recommendations
- On the independence number of random graphs
- scientific article; zbMATH DE number 5532162
- On the Strength and Independence Number of Graphs
- Maximum independent sets on random regular graphs
- On the Independent Domination Number of Random Regular Graphs
- The independent domination number of random graph
- On the independence number of random interval graphs
- The independent domination number of a random graph
- On the independent set problem in random graphs
Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Zero-one laws (60F20)
Cites Work
Cited In (26)
- A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
- Random partial orders, posts, and the causal set approach to discrete quantum gravity
- A phase transition phenomenon in a random directed acyclic graph
- Evaluating topological ordering in directed acyclic graphs
- Limit theorems for a random directed slab graph
- Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation
- Limiting properties of random graph models with vertex and edge weights
- Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models
- On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdős graph
- Searching in random partially ordered sets
- The Hilbert-Galton board
- The strong giant in a random digraph
- On the shape of a random acyclic digraph
- Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph
- Random graph orders do not satisfy a 0–1 law
- On tail distribution of interpost distance
- A Path Cover Technique for LCAs in Dags
- Convergence of directed random graphs to the Poisson-weighted infinite tree
- Barak-Erdős graphs and the infinite-bin model
- On the length of the shortest path in a sparse Barak-Erdős graph
- Two-sided infinite-bin models and analyticity for Barak-Erdős graphs
- Average-case analysis of incremental topological ordering
- Random graph orders
- A dynamic topological sort algorithm for directed acyclic graphs
- Parallel execution of schedules with random dependency graph
- Average-Case Analysis of Online Topological Ordering
This page was built for publication: On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3222867)
