IMPROVED ALGORITHMSFOR GRAPHFOUR-CONNECTNITY
Vijaya Ramachandran · 1987
We present a new .algorithm based on ear decomposition for testing vertex four-connectivity and for finding all separat ing triplets in a triconnected graph. The sequential implemen tation of our algorithm runs in 0 (n 2 ) time and the parallel implementation runs in 0 (logn) time u~ing 0 (n 2 ) processors on a CRCW PRAM, where n is the number of vertices in the graph. This· improves previous bounds for the problem for both the sequential and parallel cases. The sequential algorithm is optimal if the input is specified in adjacency matrix fonn, or if the input graph is dense.