Objekt-Metadaten

Construction sequences and certifying 3-Connectedness
Schmidt, Jens M. ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelConstruction sequences and certifying 3-Connectedness
AutorSchmidt, Jens M.
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl12 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]09,01
Freie Schlagwörterconstruction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm
DDC005 Programmierung, Programme, Daten
ZusammenfassungGiven two 3-connected graphs G and H, a construction sequence constructs G from H (e. g. from the K4) with three basic operations, called the Barnette-Gr├╝nbaum operations. These operations are known to be able to construct all 3-connected graphs. We extend this result by identifying every intermediate graph in the construction sequence with a subdivision in G and showing under some minor assumptions that there is still a construction sequence to G when we start from an arbitrary prescribed H-subdivision. This leads to the first algorithm that computes a construction sequence in time O(|V (G)|2). As an application, we develop a certificate for the 3-connectedness of graphs that can be easily computed and verified. Based on this, a certifying test on 3-connectedness is designed.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr2009
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am20.11.2009 - 12:46:57
Letzte Änderung23.01.2014 - 16:21:36
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004356
Zugriffsstatistik
 

LOADING...