## Abstract

In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let T_{d}(|V|, |E|) and P_{d}(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G = (V, E) on a PRAM model M_{d}. Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(|V| + |E|) time, and solved in parallel in O(T_{d}(|V|, |E|) + log |V|) time using O(P_{d}(|V|, |E|) + |V|/log |V|) processors on M_{d}. By constructing a decomposition tree under a CREW PRAM, we also show that T_{d}(|V|, |E|) = O(log^{2} |V|) and P_{d}(|V|, |E|) = O(|V| + |E|).

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

Pages (from-to) | 488-518 |

Number of pages | 31 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 15 |

Issue number | 4 |

DOIs | |

State | Published - Jul 2002 |

## Keywords

- Algorithms
- Data structures
- Distance-hereditary graphs
- Parallel random access machine
- Subgraph optimization problems