Objekt-Metadaten
| Construction sequences and certifying 3-Connectedness Schmidt, Jens M. ; Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik |
| Main title | Construction sequences and certifying 3-Connectedness |
| Author | Schmidt, Jens M. |
| Institution | Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik |
| No. of Pages | 12 S. |
| Series | Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]09,01 |
| Keywords | construction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm |
| Classification (DDC) | 005 Computer programming, programs, data |
| 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. |
| Documents |
pdf-Datei
If your browser can't open the file, please download the file first and then open it
|
| FU Department | Department of Mathematics and Computer Science |
| Other affiliation(s) | Institut für Informatik |
| Year of publication | 2009 |
| Type of document | Working paper |
| Language | English |
| Terms of use/Rights | Nutzungsbedingungen |
| Created at | 2009-11-20 : 12:46:57 |
| Last changed | 2015-02-27 : 08:25:18 |
| Static URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004356 |
| Statistics | |
