Treffer: Construction Sequences and Certifying 3-Connectedness
Title:
Construction Sequences and Certifying 3-Connectedness
Authors:
Contributors:
Dept. of Computer Science, Freie Universität Berlin = Free University of Berlin, Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick
Source:
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010. :633-644
Publisher Information:
CCSD, 2010.
Publication Year:
2010
Collection:
collection:STACS2010
collection:TDS-MACS
collection:TDS-MACS
Subject Terms:
removable edges, Tutte contraction, certifying algorithm, 3-connected, construction sequence, Algorithms and data structures, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.2: Graph Theory, [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs], Discrete Mathematics [cs.DM]
Subject Geographic:
Original Identifier:
HAL:
Document Type:
Konferenz
conferenceObject<br />Conference papers
Language:
English
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00455813v1
Database:
HAL
Weitere Informationen
Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Gruenbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to the K_4 can be computed in O(|V|^2) time by extending Barnette and Gruenbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.