On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph

DOI10.1137/0605049MaRDI QIDQ3222867zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

random digraphindependent vertices

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Zero-one laws (60F20)

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

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3333197 (Why is no real title available?)
• Cliques in random graphs
• On colouring random graphs

Cited in

(26)

• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Average-Case Analysis of Online Topological Ordering
• Random partial orders, posts, and the causal set approach to discrete quantum gravity
• A phase transition phenomenon in a random directed acyclic graph
• Limit theorems for a random directed slab graph
• Evaluating topological ordering in directed acyclic graphs
• Limiting properties of random graph models with vertex and edge weights
• Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation
• Searching in random partially ordered sets
• On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdős graph
• Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models
• 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
• On tail distribution of interpost distance
• Random graph orders do not satisfy a 0–1 law
• 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

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)