Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-23E5-0 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-A706-7
Genre: Hochschulschrift

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.pdf (beliebiger Volltext), 621KB
 
Datei-Permalink:
-
Name:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.ps (beliebiger Volltext), 2MB
 
Datei-Permalink:
-
Name:
Johannsen_-_Sampling_Rooted_3-Connected_Planar_Graphs_in_Deterministic_Polynomial_Time.ps
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/postscript
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Johannsen, Daniel1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2007-03-0820062006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Saarbrücken : Humboldt-Universität zu Berlin
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 314425
Anderer: Local-ID: C1256428004B93B8-9D944E28E89076EAC1257298005A5922-Johannsen2006a
 Art des Abschluß: Master

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: