An efficient parallel strategy for recognizing series-parallel graphs

Sun Yuan Hsieh, Chin Wen Ho

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

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.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings
EditorsDing-Zhu Du, Ding-Zhu Du, Xiang-Sun Zhang
PublisherSpringer Verlag
Pages496-504
Number of pages9
ISBN (Print)9783540583257
DOIs
StatePublished - 1994
Event5th Annual International Symposium on Algorithms and Computation, ISAAC 1994 - Beijing, China
Duration: 25 Aug 199427 Aug 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume834 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th Annual International Symposium on Algorithms and Computation, ISAAC 1994
Country/TerritoryChina
CityBeijing
Period25/08/9427/08/94

Fingerprint

Dive into the research topics of 'An efficient parallel strategy for recognizing series-parallel graphs'. Together they form a unique fingerprint.

Cite this