Generating labeled planar graphs uniformly at random
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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. © 2007 Elsevier Ltd. All rights reserved.
Details
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 377-386 |
Seitenumfang | 10 |
Fachzeitschrift | Theoretical computer science : the journal of the EATCS |
Jahrgang | 379 |
Ausgabenummer | 3 |
Publikationsstatus | Veröffentlicht - 15 Juni 2007 |
Peer-Review-Status | Ja |
Extern publiziert | Ja |
Externe IDs
Scopus | 34248546188 |
---|---|
ORCID | /0000-0001-8228-3611/work/142241163 |
Schlagworte
Schlagwörter
- Decomposition, Dynamic programming, Enumeration, Graph theory, Labeled planar graph, Sampling algorithm