Uniform generation of spanning regular subgraphs of a dense graph

zbMath1427.05218arXiv1807.00964MaRDI QIDQ2335698

Catherine Greenhill, Pu Gao

Publication date: 15 November 2019

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

Full work available at URL: https://arxiv.org/abs/1807.00964

zbMATH Keywords

enumerationswitching methoduniform generation\(d\)-factors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sequential algorithm for generating random graphs
• Fast uniform generation of regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• The asymptotic number of labeled graphs with given degree sequences
• Asymptotic enumeration by degree sequence of graphs of high degree
• Uniform generation of \(d\)-factors in dense host graphs
• Subgraphs of Dense Random Graphs with Specified Degrees
• Approximating the Permanent
• Uniform generation of random regular graphs of moderate degree
• Uniform generation of random graphs with power-law degree sequences
• Generating Random Regular Graphs Quickly
• Uniform Generation of Random Regular Graphs
• Sampling Regular Graphs and a Peer-to-Peer Network
• Asymptotic Enumeration of Hypergraphs by Degree Sequence
• Generating random regular graphs

This page was built for publication: Uniform generation of spanning regular subgraphs of a dense graph