Generating labeled planar graphs uniformly at random

作     者：Bodirsky, Manuel Groepl, Clemens Kang, Mihyun 

作者机构：Free Univ Berlin Inst Informat D-14195 Berlin Germany Humboldt Univ Inst Informat Abt Algorithmen & Komplexitat 1 D-10099 Berlin Germany 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2007年第379卷第3期

页      面：377-386页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Berlin Center for Genome Based Bioinformatics Deutsche Forschungsgemeinschaft, DFG, (GRK 588/2, Pr 296/3, Pr 413/1-2) Bundesministerium für Bildung und Forschung, BMBF, (031 2705A) 

主　　题：labeled planar graph enumeration decomposition sampling algorithm dynamic programming graph theory 

摘      要：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. (c) 2007 Elsevier B.V. All rights reserved.