Improved algorithms for graph four- connectivity

摘要

We present a new algorithm based on open ear decomposition for testing vertex four-connectivity and for finding all separating triplets in a triconnected graph. A sequential implementation of our algorithm runs in O(n2) time and a parallel implementation runs in O(log2 n) time using O(n2) processors on an ARBITRARY CRCW PRAM, where n is the number of vertices in the graph. This improves previous bounds for the problem for both the sequential and the parallel cases. The sequential time bound is the best possible, to within a constant factor, if the input is specified in adjacency matrix form, or if the input graph is dense.