Generating labeled planar graphs uniformly at random

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Manuel Bodirsky - , Humboldt-Universität zu Berlin (Autor:in)
  • Clemens Gröpl - (Autor:in)
  • Mihyun Kang - (Autor:in)

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

OriginalspracheEnglisch
Seiten (von - bis)377-386
Seitenumfang10
FachzeitschriftTheoretical computer science : the journal of the EATCS
Jahrgang379
Ausgabenummer3
PublikationsstatusVeröffentlicht - 15 Juni 2007
Peer-Review-StatusJa
Extern publiziertJa

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

Bibliotheksschlagworte