Name
Title | ||
|---|---|---|
An unbiased pointing operator for unlabeled structures, with applications to counting and sampling |
Abstract | ||
|---|---|---|
We introduce a general method to count and randomly sample unlabeled combinatorial structures. The approach is based on pointing unlabeled structures in an "unbiased" way, i.e., in such a way that a structure of size n gives rise to n pointed structures. We develop a specific Pólya theory for the corresponding pointing operator, and present a sampling framework relying both on the principles of Boltzmann sampling and on Pólya operators. Our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and non-plane unrooted trees, and tree-like structures in general, but also to cactus graphs, outerplanar graphs, RNA secondary structures, and classes of planar maps. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.5555/1283383.1283421 | SODA |
Keywords | Field | DocType |
lya theory,sample unlabeled combinatorial structure,lya operator,unlabeled family,sampling framework,specific p,size n,unlabeled structure,general method,boltzmann sampling,rna secondary structure,outerplanar graph | Discrete mathematics,Graph,Combinatorics,Multicast scheduling,Computer science,Algorithm,Planar,Operator (computer programming),Sampling (statistics) | Conference |
ISBN | Citations | PageRank |
978-0-89871-624-5 | 6 | 0.67 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Eric Fusy | 2 | 22 | 2.40 |
| Mihyun Kang | 3 | 163 | 29.18 |
| Stefan Vigerske | 4 | 119 | 10.85 |