RNC algorithms for the uniform generation of combinatorial structures

Michele Zito, Ida Pu, Martyn Amos, Alan Gibbons

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

We describe several RNC algorithms for generating graphs and subgraphs uniformly at random. For example, unla-belled undirected graphs are generated in O(lg3 n lg lg n) time using O (ϵn1.5/lg3n lg lg n) processors if their number is known in advance and in O(lg n) time using O(ϵn2/lg n) processors otherwise. In both cases the error probability is the inverse of a polynomial in ϵ. Thus ϵ may be chosen to trade-off processors for error probability. Also, for an arbitrary graph, we describe RNC algorithms for the uniform generation of its subgraphs that are either non-simple paths or spanning trees. The work measure for the subgraph algorithms is essentially determined by the transitive closure bottleneck. As for sequential algorithms, the general notion of constructing generators from counters also applies to parallel algorithms although this approach is not employed by all the algorithms of this paper.

Original languageEnglish
Title of host publicationProceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
PublisherACM
Pages429-437
Number of pages9
VolumePart F129447
ISBN (Electronic)0898713668
Publication statusPublished - 28 Jan 1996
Externally publishedYes
Event7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996 - Atlanta, United States
Duration: 28 Jan 199630 Jan 1996

Conference

Conference7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996
CountryUnited States
CityAtlanta
Period28/01/9630/01/96

Fingerprint Dive into the research topics of 'RNC algorithms for the uniform generation of combinatorial structures'. Together they form a unique fingerprint.

Cite this