Characterization of efficiently parallel solvable problems on a class of decomposable graphs

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

In this paper, we sketch characteristics of those problems which can be systematically solved on decomposable graphs. Trees, series-parallel graphs, outerplanar graphs, and bandwidth-k graphs all belong to decomposable graphs. Let Td(|V|,|E|) and Pd(|V|,|E|) denote the time complexity and processor complexity required to construct a parse tree representation TG for a decomposable G = (V, E) on a PRAM model Md. We define a general problem-solving paradigm to solve a wide class of subgraph optimization problems on decomposable graphs in O(Td(|V|,|E|) + log|V(TG)|) time using O(Pd(|V|,|E|) + |V(T G)|/log|V(TG)|) processors on Md. By using our paradigm, we show the following parallel complexities: (a) The maximum independent set problem on trees can be solved in O(log|V|) time using O(|V|/log|V|) processors on an EREW PRAM, (b) The maximum matching problem on series-parallel, graphs can be solved in O(log|E|) time using O(|E|/log|E|) processors on an EREW PRAM, (c) The efficient domination problem on series-parallel graphs can be solved in O(log|E|) time using O(|E|/log|E|) processors on an EREW PRAM.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsMarian Bubak, Geert Dick van Albada, Peter M.A. Sloot, Jack J. Dongarra
PublisherSpringer Verlag
Pages223-230
Number of pages8
ISBN (Print)9783540221142
DOIs
Publication statusPublished - 2004 Jan 1

Publication series

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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Characterization of efficiently parallel solvable problems on a class of decomposable graphs'. Together they form a unique fingerprint.

  • Cite this

    Hsieh, S. Y. (2004). Characterization of efficiently parallel solvable problems on a class of decomposable graphs. In M. Bubak, G. D. van Albada, P. M. A. Sloot, & J. J. Dongarra (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 223-230). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3036). Springer Verlag. https://doi.org/10.1007/978-3-540-24685-5_28