Paper Info
Title
An Efficient Parallel Strategy for Recognizing Series-Parallel Graphs
Abstract
An efficient parallel algorithm for recognizing series-parallel (SP) graphs on a CRCW PRAM is presented. The time complexity of the algorithm is O(log n), and the number of processors used is O((m + n) loglog n/log n), where n is the number of vertices and m is the number of edges of the input graph. This paper develops a new methodology of recognition for SP graphs, based on open ear decomposition, that improves the complexity found in previous results. Another emphasis in our algorithms is placed on the construction of decomposition trees for SP graphs. Some interesting properties of SP graphs are derived in order to facilitate fast parallel processing.
Year
DOI
Venue
1994
10.1007/3-540-58325-4_216
ISAAC
Keywords
Field
DocType
efficient parallel strategy,recognizing series-parallel graphs,time complexity,parallel processing,series parallel,parallel algorithm
Analysis of parallel algorithms,Binary logarithm,Discrete mathematics,Combinatorics,Vertex (geometry),Computer science,Massively parallel,Parallel algorithm,Ear decomposition,Series and parallel circuits,Time complexity
Conference
ISBN
Citations 
PageRank 
3-540-58325-4
0
0.34
References 
Authors
10
2
Name
Order
Citations
PageRank
Sun-Yuan Hsieh11715112.85
Chin-Wen Ho257339.27