English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time

Johannsen, D. (2006). Sampling Rooted 3-Connected Planar Graphs in Deterministic Polynomial Time. Master Thesis, Humboldt-Universität zu Berlin, Saarbrücken.

Item is

Files

show Files
hide Files
:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.pdf (Any fulltext), 621KB
 
File Permalink:
-
Name:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-
:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.ps (Any fulltext), 2MB
 
File Permalink:
-
Name:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.ps
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/postscript
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Johannsen, Daniel1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: In this thesis an algorithm for sampling rooted 3-connected planar graphs (c-nets) in deterministic polynomial time is presented. The algorithm is based on a decomposition strategy for c-nets, which is formulated as a system of bijections between classes of c-nets parameterized by the number of vertices, faces, and edges on the outer face. This system is then used in three ways: First, as system of recursive equations to derive the sizes of above classes by using an algorithm based on dynamic programming. Second, as system of equations of generating functions to derive an algebraic generating function and a single parameter recursion formula for c-nets. Third, as composition scheme to sample c-nets uniformly at random with the recursive method of sampling. The thesis is based on the paper \emph{A Direct Decomposition of 3-connected Planar Graphs} by Manuel Bodirsky, Clemens Gr{\"o}pl, Mihyun Kang and the author~\cite{3connplanar} and extends it by the parameter for the number of edges and a full proof of the decomposition.

Details

show
hide
Language(s): eng - English
 Dates: 2007-03-0820062006
 Publication Status: Issued
 Pages: -
 Publishing info: Saarbrücken : Humboldt-Universität zu Berlin
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 314425
Other: Local-ID: C1256428004B93B8-9D944E28E89076EAC1257298005A5922-Johannsen2006a
 Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show