Of particular interest are polynomial time sampling algorithms and enumeration algorithms.
Sampling, in other words, random generation, plays an important role in combinatorics and in computer science as well as in statistical mechanics. It is sometimes the case that only random generation algorithms can provide possible (approximate) solutions for certain hard combinatorial problems. The well-known techniques for sampling include the recursive method, Markov chain Monte Carlo method, and Boltzmann sampler.
Using the recursive method and Boltzmann sampler we design efficient sampling algorithms to generate a random instance uniformly at random from labeled or unlabeled planar structures, e.g., planar graphs, cubic planar graphs, and outerplanar graphs.
Along the sampling algorithms the recursive method provides also algorithms to compute the exact numbers of labeled or unlabeled planar structures in polynomial time.
Sampling, in other words, random generation, plays an important role in combinatorics and in computer science as well as in statistical mechanics. It is sometimes the case that only random generation algorithms can provide possible (approximate) solutions for certain hard combinatorial problems. The well-known techniques for sampling include the recursive method, Markov chain Monte Carlo method, and Boltzmann sampler.
Using the recursive method and Boltzmann sampler we design efficient sampling algorithms to generate a random instance uniformly at random from labeled or unlabeled planar structures, e.g., planar graphs, cubic planar graphs, and outerplanar graphs.
Along the sampling algorithms the recursive method provides also algorithms to compute the exact numbers of labeled or unlabeled planar structures in polynomial time.
- Generating labeled planar graphs uniformly at random
- A direct decomposition of 3-connected planar graphs
- Generating outerplanar graphs uniformly at random
- Generating unlabeled connected cubic planar graphs uniformly at random
- Sampling unlabeled biconnected planar graphs
- An unbiased pointing operator for unlabeled structures with applications to counting and sampling
