TY - JOUR
T1 - Efficiently parallelizable problems on a class of decomposable graphs
AU - Hsieh, Sun Yuan
PY - 2005/2
Y1 - 2005/2
N2 - In the literature, there are quite a few sequential and parallel algorithms to solve problems on decomposable graphs utilizing distinct techniques. 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 graph 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(P d(|V|, |E|) + |V(TG)|)/log|V(TG)|)) processors on Md. We also demonstrate the following examples fitting into our paradigm: (1) The maximum independent set problem on trees, (2) The maximum matching problem on series-parallel graphs, and (3) The efficient domination problem on series-parallel graphs. Our results improve the previously best known results of (1) and (2).
AB - In the literature, there are quite a few sequential and parallel algorithms to solve problems on decomposable graphs utilizing distinct techniques. 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 graph 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(P d(|V|, |E|) + |V(TG)|)/log|V(TG)|)) processors on Md. We also demonstrate the following examples fitting into our paradigm: (1) The maximum independent set problem on trees, (2) The maximum matching problem on series-parallel graphs, and (3) The efficient domination problem on series-parallel graphs. Our results improve the previously best known results of (1) and (2).
UR - http://www.scopus.com/inward/record.url?scp=9244262455&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=9244262455&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2004.08.003
DO - 10.1016/j.jcss.2004.08.003
M3 - Article
AN - SCOPUS:9244262455
VL - 70
SP - 140
EP - 156
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
IS - 1
ER -