𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex-Pursuit in Random Directed Acyclic Graphs

✍ Scribed by Bonato, Anthony; Mitsche, Dieter; Prałat, Paweł

Book ID
120362588
Publisher
Society for Industrial and Applied Mathematics
Year
2013
Tongue
English
Weight
313 KB
Volume
27
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Vertex-to-vertex pursuit in a graph
Vertex-to-vertex pursuit in a graph
✍ Richard Nowakowski; Peter Winkler 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 612 KB

A graph G is given and two players, a cop and a robber, play the folioking game: the cop chooses a vertex, then the robber chooses a vertex, then the players move alternately beginning with the cop. A move consists of staying at one's present vertex or moving to an adjacent vertex; each move is seen

A phase transition phenomenon in a rando
A phase transition phenomenon in a random directed acyclic graph
✍ B. Pittel; R. Tungol 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

Let a random directed acyclic graph be defined as being obtained from the random graph G n p by orienting the edges according to the ordering of vertices. Let γ \* n be the size of the largest (reflexive, transitive) closure of a vertex. For p = c log n /n, we prove that, with high probability, γ \*