TY - CHAP

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

AU - Hsieh, Sun Yuan

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35048887499&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048887499&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24685-5_28

DO - 10.1007/978-3-540-24685-5_28

M3 - Chapter

AN - SCOPUS:35048887499

SN - 9783540221142

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 223

EP - 230

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Bubak, Marian

A2 - van Albada, Geert Dick

A2 - Sloot, Peter M.A.

A2 - Dongarra, Jack J.

PB - Springer Verlag

ER -