A parallel algorithm for finding a triconnected component separator with an application (Q1339375)

A separator of an \(n\)-vertex graph \(G\) is a set \(S\) of vertices of \(G\) such that the graph obtained by removing all vertices of \(S\) from \(G\) has no connected component with more than \({2\over 3} n\) vertices. A triconnected component separator of a biconnected graph \(G\) is a separator that is the vertex set of some triconnected component of \(G\). It is shown in this article that every graph \(G\) has a separator \(S\) such that \(S\) is the vertex set of either a bridge of \(G\) or a triconnected component of some biconnected component of \(G\) and such a separator can be found in \(O(\log n)\) time with \(O(m\log\log n/\log n)\) processors on a concurrent-read concurrent-write parallel random access machine (CRCW PRAM). This result improves Khuller's result.