| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Construction Sequences and Certifying 3-Connectedness
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.
Cited literature [16 references]
https://hal.inria.fr/inria-00455813
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, February 11, 2010 - 11:56:17 AM
Last modification on : Thursday, January 6, 2022 - 12:14:04 PM
Long-term archiving on: : Friday, June 18, 2010 - 8:14:04 PM
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Thursday, February 11, 2010 - 11:56:17 AM
Last modification on : Thursday, January 6, 2022 - 12:14:04 PM
Long-term archiving on: : Friday, June 18, 2010 - 8:14:04 PM
File
Schmidt.pdf
Files produced by the author(s)