### Abstract

In the literature, there are quite a few sequential and parallel algorithms to solve problems in a distance-hereditary graph G utilizing techniques discovered from the properties of the problems. Based on structural properties of G, we first sketch characteristics of problems which can be systematic solved on G and then define a general problem-solving paradigm. Given a decomposition tree representation of G, we propose a unified approach to construct sequential dynamic-programming algorithms for several fundamental graph-theoretical problems that fit into our paradigm. We also show that our sequential solutions can be efficiently parallelized using the tree contraction technique.

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

Title of host publication | Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings |

Pages | 257-266 |

Number of pages | 10 |

Publication status | Published - 1998 Dec 1 |

Event | 9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of Duration: 1998 Dec 14 → 1998 Dec 16 |

### Publication series

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

Volume | 1533 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 9th Annual International Symposium on Algorithms and Computation, ISAAC'98 |
---|---|

Country | Korea, Republic of |

City | Taejon |

Period | 98-12-14 → 98-12-16 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Characterization of efficiently solvable problems on distance-hereditary graphs'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings*(pp. 257-266). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1533 LNCS).