Construction Sequences and Certifying 3-connectivity
Construction Sequences and Certifying 3-connectivity
复制标题
施工顺序和认证 3-连通性
DOI：
10.1007/s00453-010-9450-9
复制
发表时间：
2012
期刊：
影响因子：
1.1
通讯作者：
Jens M. Schmidt
中科院分区：
文献类型：
--
作者：
Jens M. Schmidt
Tutte证明了每个超过4个顶点的3点连通图G都有一个可缩边。Barnette和Grünbaum证明了在相同的背景下存在可移除的边。我们证明了通过推广Barnette和Grünbaum定理，可以在O(|V|2)时间内计算出从G到K4的收缩序列和去掉序列。作为应用，我们给出了一个易于计算和验证的图的3-点连通度证书。
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 K4 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.