Generating labeled planar graphs uniformly at random |
| |
| Authors: | Manuel Bodirsky,Clemens Grö pl,Mihyun Kang |
| |
| Affiliation: | 1. Humboldt-Universität zu Berlin, Institut für Informatik, Abteilung Algorithmen und Komplexität I, Unter den Linden 6, 10099 Berlin, Germany;2. Freie Universität Berlin, Institut für Informatik, Algorithmische Bioinformatik, Takustraße 9, 14195 Berlin, Germany |
| |
| 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. |
| |
| Keywords: | Labeled planar graph Enumeration Decomposition Sampling algorithm Dynamic programming Graph theory |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
