Quadratic exact-size and linear approximate-size random generation of planar graphs

Quadratic exact-size and linear approximate-size random generation of planar graphs

This extended abstract introduces a new algorithm for the random generation of labelled planar graphs. Its principles rely on Boltzmann samplers as recently developed by Duchon, Flajolet, Louchard, and Schaeffer. It combines the Boltzmann framework, a judicious use of rejection, a new combinatorial...

Full description

Bibliographic Details
Main Author: Eric Fusy
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2005-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
planar graphs
boltzmann samplers
rejection sampling
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
[info.info-hc] computer science [cs]/human-computer interaction [cs.hc]
Online Access:https://dmtcs.episciences.org/3362/pdf

Internet

https://dmtcs.episciences.org/3362/pdf

Similar Items