Construction Sequences and Certifying 3-Connectedness

Jens M. Schmidt 1, *
* Auteur correspondant
1 Dept. of Computer Science
Abstract : 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.
Keywords : Algorithms and data structures construction sequence 3-connected certifying algorithm Tutte contraction removable edges
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.633-644, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00455813
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 11:56:17
Dernière modification le : mercredi 29 novembre 2017 - 10:26:32
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:14:04

Fichier

Schmidt.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455813, version 1

Collections

STACS2010 | TDS-MACS

Citation

Jens M. Schmidt. Construction Sequences and Certifying 3-Connectedness. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.633-644, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455813〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

136

Téléchargements de fichiers

81

Contact


archive-ouverte@inria.fr