Uniform Sampling of Digraphs with a Fixed Degree Sequence

DOI10.1007/978-3-642-16926-7_21zbMath1309.68145OpenAlexW1541582128WikidataQ57013232 ScholiaQ57013232MaRDI QIDQ3057627

Annabell Berger, Matthias Müller-Hannemann

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_21

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) 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)

Related Items (5)

Mixing time of the switch Markov chain and stable degree sequences ⋮ Unnamed Item ⋮ The switch Markov chain for sampling irregular graphs and digraphs ⋮ The mixing time of switch Markov chains: a unified approach ⋮ Split digraphs

Cites Work

• A sequential algorithm for generating random graphs
• A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• On the realization of a (p,s)-digraph with prescribed degrees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the degrees of the vertices of a directed graph
• Algorithms for constructing graphs and digraphs with given valences and factors
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• A remark on the existence of finite graphs
• Combinatorial Properties of Matrices of Zeros and Ones
• Uniform generation of random regular graphs of moderate degree
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Generating Random Regular Graphs Quickly
• Sampling Regular Graphs and a Peer-to-Peer Network
• Network Analysis
• The Factors of Graphs
• Sampling binary contingency tables with a greedy start
• Generating random regular graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Uniform Sampling of Digraphs with a Fixed Degree Sequence