## Abstract

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 T_{d}(|V|, |E|) and P_{d}(|V|, |E|) denote the time complexity and processor complexity required to construct a parse tree representation T_{G} for a decomposable graph G = (V, E) on a PRAM model M_{d}. We define a general problem-solving paradigm to solve a wide class of subgraph optimization problems on decomposable graphs in O(T_{d}(|V|, |E|) + log |V(T_{G})|) time using O(P _{d}(|V|, |E|) + |V(T_{G})|)/log|V(T_{G})|)) processors on M_{d}. 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).

Original language | English |
---|---|

Pages (from-to) | 140-156 |

Number of pages | 17 |

Journal | Journal of Computer and System Sciences |

Volume | 70 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2005 Feb |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics