Bodirsky, M. and Gröpl, C. and Kang, M. (2007) Generating labeled planar graphs uniformly at random. Theoretical Computer Science, 379 (3). pp. 377-386.
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/B6V1G...
Abstract
We present a deterministic polynomial time algorithm to sample a labeled planar graph uniformly at random. Our approach uses recursive formulae for the exact number of labeled planar graphs with n vertices and m edges, based on a decomposition into 1-, 2-, and 3-connected components. We can then use known sampling algorithms and counting formulae for 3-connected planar graphs.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Labeled planar graph, Enumeration, Decomposition, Sampling algorithm, Dynamic programming, Graph theory |
| Subjects: | Mathematical and Computer Sciences > Computer Science |
| Divisions: | Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group |
| ID Code: | 339 |
| Deposited By: | Admin Administrator |
| Deposited On: | 14 Apr 2009 14:19 |
| Last Modified: | 14 Apr 2009 14:19 |
Repository Staff Only: item control page
