Uniform generation of random regular graphs

Pu Gao; Nicholas Wormald

doi:10.1109/FOCS.2015.78

Uniform generation of random regular graphs

Pu Gao
, Nicholas Wormald

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review

12 Citations (Scopus)

Abstract

We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler A for d-regular graphs. A can be implemented such that each graph is generated in expected time O(nd3), provided that d = o (√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler B, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).

Original language	English
Title of host publication	Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	1218-1230
Number of pages	13
ISBN (Electronic)	9781467381918
DOIs	https://doi.org/10.1109/FOCS.2015.78
Publication status	Published - 11 Dec 2015
Event	IEEE Symposium on Foundations of Computer Science 2015 - DoubleTree Hotel at the Berkeley Marina, Berkeley, United States of America Duration: 17 Oct 2015 → 20 Oct 2015 Conference number: 56th

Conference

Conference	IEEE Symposium on Foundations of Computer Science 2015
Abbreviated title	FOCS 2015
Country/Territory	United States of America
City	Berkeley
Period	17/10/15 → 20/10/15

Keywords

Markov chain
regular graphs
switching
uniform generation

Access to Document

10.1109/FOCS.2015.78

Cite this

@inproceedings{d5eba51815e84a2fa97510b47196cccf,

title = "Uniform generation of random regular graphs",

abstract = "We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler A for d-regular graphs. A can be implemented such that each graph is generated in expected time O(nd3), provided that d = o (√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler B, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).",

keywords = "Markov chain, regular graphs, switching, uniform generation",

author = "Pu Gao and Nicholas Wormald",

year = "2015",

month = dec,

day = "11",

doi = "10.1109/FOCS.2015.78",

language = "English",

pages = "1218--1230",

booktitle = "Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)",

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

address = "United States of America",

note = "IEEE Symposium on Foundations of Computer Science 2015, FOCS 2015 ; Conference date: 17-10-2015 Through 20-10-2015",

}

Gao, P & Wormald, N 2015, Uniform generation of random regular graphs. in Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015). IEEE, Institute of Electrical and Electronics Engineers, pp. 1218-1230, IEEE Symposium on Foundations of Computer Science 2015, Berkeley, California, United States of America, 17/10/15. https://doi.org/10.1109/FOCS.2015.78

TY - GEN

T1 - Uniform generation of random regular graphs

AU - Gao, Pu

AU - Wormald, Nicholas

N1 - Conference code: 56th

PY - 2015/12/11

Y1 - 2015/12/11

N2 - We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler A for d-regular graphs. A can be implemented such that each graph is generated in expected time O(nd3), provided that d = o (√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler B, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).

AB - We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler A for d-regular graphs. A can be implemented such that each graph is generated in expected time O(nd3), provided that d = o (√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler B, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).

KW - Markov chain

KW - regular graphs

KW - switching

KW - uniform generation

UR - https://www.scopus.com/pages/publications/84960352860

U2 - 10.1109/FOCS.2015.78

DO - 10.1109/FOCS.2015.78

M3 - Conference Paper

AN - SCOPUS:84960352860

SP - 1218

EP - 1230

BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)

PB - IEEE, Institute of Electrical and Electronics Engineers

T2 - IEEE Symposium on Foundations of Computer Science 2015

Y2 - 17 October 2015 through 20 October 2015

ER -

Uniform generation of random regular graphs

Abstract

Conference

Keywords

Access to Document

Other files and links

Research output

Uniform generation of random regular graphs

Cite this