𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Random Generation of Directed Acyclic Graphs

✍ Scribed by G. Melançon; I. Dutour; M. Bousquet-Mélou

Book ID
108498012
Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
301 KB
Volume
10
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Acyclic Orientations of Random Graphs
Acyclic Orientations of Random Graphs
✍ C.M Reidys 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 195 KB

An acyclic orientation of an undirected graph is an orientation of its edges such that the resulting directed graph contains no cycles. The random graph G is a n, p probability space consisting of subgraphs of K that are obtained by selecting each n K -edge with independent probability p. The random

The generalized acyclic edge chromatic n
The generalized acyclic edge chromatic number of random regular graphs
✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

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, γ \*