Construction Sequences and Certifying 3‐connectivity

Construction Sequences and Certifying 3‐connectivity

0.00 Avg rating0 Votes
Article ID: iaor2012388
Volume: 62
Issue: 1
Start Page Number: 192
End Page Number: 208
Publication Date: Feb 2012
Journal: Algorithmica
Authors:
Abstract:

Tutte proved that every 3‐vertex‐connected graph G on more than 4 vertices has a contractible edge. Barnette and Grünbaum 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 K 4 can be computed in O(|V|2) time by extending Barnette’s and Grünbaum’s theorem. As an application, we derive a certificate for the 3‐vertex‐connectivity of graphs that can be easily computed and verified.

Reviews

Required fields are marked *. Your email address will not be published.