@inproceedings{cd3b87ef6be94390a0065446659d9f25,

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.",

author = "Hsieh, {Sun Yuan} and Ho, {Chin Wen}",

note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; null ; Conference date: 25-08-1994 Through 27-08-1994",

year = "1994",

doi = "10.1007/3-540-58325-4_216",

language = "???core.languages.en_GB???",

isbn = "9783540583257",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "496--504",

editor = "Ding-Zhu Du and Ding-Zhu Du and {Zhang }, Xiang-Sun",

booktitle = "Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings",

}