A parallel algorithm for finding a triconnected component separator with an application (Q1339375): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q220283 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Anatoly V. Anisimov / rank | |||
Normal rank |
Revision as of 23:37, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A parallel algorithm for finding a triconnected component separator with an application |
scientific article |
Statements
A parallel algorithm for finding a triconnected component separator with an application (English)
0 references
29 September 1996
0 references
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.
0 references
biconnected graph
0 references
separator
0 references