论文标题
一种简单的认证算法，用于3边缘连接性
A simple certifying algorithm for 3-edge-connectivity
论文作者
论文摘要
提出了用于3边缘连接性的线性时间认证算法。给定给定图G的给定图G，如果G是3边缘连接的，则该算法会生成一个构造顺序作为G的正证书。图收缩技术。而且，该图不必是2边连接的。
A linear-time certifying algorithm for 3-edge-connectivity is presented. Given an undirected graph G, if G is 3-edge-connected, the algorithm generates a construction sequence as a positive certificate for G. Otherwise, the algorithm decomposes G into its 3-edge-connected components and at the same time generates a construction sequence for each connected component as well as the bridges and a cactus representation of the cut-pairs in G. All of these are done by making only one pass over G using an innovative graph contraction technique. Moreover, the graph need not be 2-edge-connected.
