|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 8 van 13 gevonden artikelen
| Titel: |
FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHS |
| Auteur: |
Nikolopoulos, Stavros D. Danielopoulos, Stylianos D. |
| Verschenen in: |
International journal of parallel, emergent and distributed systems |
| Paginering: | Jaargang 3 (1994) nr. 1-2 pagina's 45-55 |
| Jaar: |
1994 |
| Inhoud: |
In this paper we present fast parallel algorithms for finding the cutpoints and bridges of an undirected graph G = (V,E) having n vertices. We start with the notion of partitioning a graph in a set of (mutually disjoint) adjacency-level sets, and we propose a parallel algorithm which computes these sets in time O(logL) using L · H · n2 processors on a CRCW-PRAM, where L < n and H < n. Based on the properties of the adjacency-level sets, we formulate parallel algorithms which locate all cutpoints and bridges of an undirected graph in constant time O(1) by using no more than L · H · n2 processors on a CRCW-PRAM computational model. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 8 van 13 gevonden artikelen
| << vorige | volgende >> |