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 | |