Efficiently parallelizable problems on a class of decomposable graphs

摘要

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(Pd(|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).