### 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 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 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}. 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 language | English |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Marian Bubak, Geert Dick van Albada, Peter M.A. Sloot, Jack J. Dongarra |

Publisher | Springer Verlag |

Pages | 223-230 |

Number of pages | 8 |

ISBN (Print) | 9783540221142 |

DOIs | |

Publication status | Published - 2004 Jan 1 |

### Publication series

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

Volume | 3036 |

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

*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