A parallel algorithm for finding a triconnected component separator with an application
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.
- A fast parallel algorithm for the maximal independent set problem
- An approach to the subgraph homeomorphism problem
- An Efficient Parallel Biconnectivity Algorithm
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
- Extending planar graph algorithms to \(K_{3,3}\)-free graphs
- Finding Triconnected Components by Local Replacement
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
This page was built for publication: A parallel algorithm for finding a triconnected component separator with an application
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1339375)
