The subject is the 3-edge-connectivity augmentation problem. Given an undirected multi-graph G/sub 0/=(V, E), find an edge set E' of minimum cardinality such that the graph (V, E union E') is 3-edge-connected, where each edge of E' connects vertices of V. The authors propose an O( mod V mod + mod E mod ) augmenting algorithm for the problem. It finds a solution to the 3-edge-connectivity augmentation problem if all k-components (k>or=3) of G/sub 0/ are available.
展开▼
机译：主题是3边连通性增加问题。给定无向多图G / sub 0 / =（V，E），找到最小基数的边集E'，使得图（V，E union E'）被3边连接，其中图的每个边E'连接V的顶点。作者针对该问题提出了O（mod V mod + mod E mod）扩充算法。如果G / sub 0 /的所有k分量（k> or = 3）都可用，则可以找到3边连通性增加问题的解决方案。
展开▼
