Parallel Complexity of the Connected Subgraph Problem
This paper shows that the problem of testing whether a graph $G$ contains an induced subgraph of vertex (edge) connectivity at least $k$ is P-complete for any fixed $k \geqslant 3$. Moreover, if $k_{\...
This paper shows that the problem of testing whether a graph $G$ contains an induced subgraph of vertex (edge) connectivity at least $k$ is P-complete for any fixed $k \geqslant 3$. Moreover, if $k_{\...
Improved Parallel Polynomial Division
The authors compute the first $N$ coefficients of the reciprocal $r(x)$, $r(x)p(x) = 1\bmod x^N $ (given a natural $N$ and a polynomial $p(x)$), $(p(0) \ne 0)$, by using $O(h\log N)$ arithmetic steps ...
The authors compute the first $N$ coefficients of the reciprocal $r(x)$, $r(x)p(x) = 1\bmod x^N $ (given a natural $N$ and a polynomial $p(x)$), $(p(0) \ne 0)$, by using $O(h\log N)$ arithmetic steps ...
You are not logged in to this journal. Log in
Finding Triconnected Components by Local Replacement
SIAM J. Comput. Volume 22, Issue 3, pp. 587-616 (1993)
Issue Date: 1993
Connotea
CiteULike
del.icio.us
BibSonomy
A parallel algorithm for finding triconnected components on a CRCW PRAM is presented. The time complexity of the algorithm is $O(\log n)$, and the processor-time product is $O((m + n)\log \log n)$, where $n$ is the number of vertices and $m$ is the number of edges of the input graph. The algorithm, like other parallel algorithms for this problem, is based on open ear decomposition, but it uses a new technique, local replacement, to improve the complexity. Only the need to use the subroutines for connected components and integer sorting, for which no optimal parallel algorithm that runs in $O(\log n)$ time is known, prevents the algorithm from achieving optimality.
©1993 (Copyright) Society for Industrial and Applied Mathematics
| History: | Received 1990-03-15; accepted 1992-03-06 |
| Permalink: | http://dx.doi.org/10.1137/0222040 |
KEYWORDS and AMS
05C40, 68Q22, 90B12
PUBLICATION DATA
0097-5397 (print)
1095-7111 (online)
SIAM