Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs

DOI10.37236/12250MaRDI QIDQ6864226zbMATH OpenFDO

Authors Martin Pépin, Alfredo Viola

Publication date 4 February 2026

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.37236/12250

zbMATH Keywords

data structuresrandom generation of classical labelled DAGs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cites work

• scientific article; zbMATH DE number 3130608 (Why is no real title available?)
• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 177816 (Why is no real title available?)
• scientific article; zbMATH DE number 3585466 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 3348134 (Why is no real title available?)
• scientific article; zbMATH DE number 3409391 (Why is no real title available?)
• A comparison of random task graph generation methods for scheduling problems
• Acyclic orientations of graphs
• Analytic combinatorics
• Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic
• Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language
• Asymptotics of relaxed k-ary trees
• Bipolar orientations on planar maps and \(\mathrm{SLE}_{12}\)
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Compacted binary trees admit a stretched exponential
• Counting acyclic digraphs by sources and sinks
• Efficient Sampling and Structure Learning of Bayesian Networks
• Enumerative applications of a decomposition for graphs and digraphs
• On programming of arithmetic operations
• Random Generation of Directed Acyclic Graphs
• Random generation of Git graphs
• Symbolic method and directed graph enumeration
• The random generation of directed animals
• The theory of the G-function.
• Theoretical Analysis of Git Bisect
• Tools and Algorithms for the Construction and Analysis of Systems
• Uniform random generation of large acyclic digraphs
• Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling
• XML compression via directed acyclic graphs

This page was built for publication: Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6864226)