Markov chain algorithms for generating sets uniformly at random

DOI10.26493/1855-3974.286.93AMaRDI QIDQ2925425zbMATH OpenOpenAlexWikidataFDO

Authors Alberto Policriti, Alexandru I. Tomescu

Publication date 22 October 2014

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://doi.org/10.26493/1855-3974.286.93a

zbMATH Keywords

Markov chainrandom generationtransitive setextensional digraph

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Random walks on graphs (05C81) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Recommendations

• Generating connected acyclic digraphs uniformly at random
• Random Generation of Directed Acyclic Graphs
• Random generation of deterministic acyclic automata using Markov chains
• Sampling different kinds of acyclic automata using Markov chains
• Ranking, unranking and random generation of extensional acyclic digraphs

Cited in

(3)

• Random Generation of Directed Acyclic Graphs
• Is hyper-extensionality preservable under deletions of graph elements?
• Random generation of deterministic acyclic automata using Markov chains

This page was built for publication: Markov chain algorithms for generating sets uniformly at random

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