Navigation/Menü: Links auf weitere Seiten dieser Website
Objekt-Metadaten
| Construction sequences and certifying 3-Connectedness Schmidt, Jens M. |
| Haupttitel | Construction sequences and certifying 3-Connectedness |
| Autor | Schmidt, Jens M. |
| Seitenzahl | 12 S. |
| Schriftenreihe | Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]09,01 |
| Fachbereich/Einrichtung | FB Mathematik und Informatik |
| Arbeitsbereich/Institut | Institut für Informatik |
| Erscheinungsjahr | 2009 |
| Dokumente | pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
| Freie Schlagwörter | construction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm |
| DDC | 005 Programmierung, Programme, Daten |
| Dokumententyp/-Sammlungen | Report |
| Medientyp/Format | Text |
| Abstract | Given 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. |
| Sprache | Englisch |
| Rechte | Nutzungsbedingungen |
| Zugriffstatistik | |
| Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004356 |
| Erstellt am | 20.11.2009 - 13:46:57 |
| Letzte Änderung | 04.04.2013 - 09:33:29 |
