Characterization of efficiently solvable problems on distance-hereditary graphs

Sun-Yuan Hsieh, Chin Wen Ho, Tsan Sheng Hsu, Ming Tat Ko, Gen Huey Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

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 languageEnglish
Title of host publicationAlgorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings
Pages257-266
Number of pages10
Publication statusPublished - 1998 Dec 1
Event9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of
Duration: 1998 Dec 141998 Dec 16

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1533 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th Annual International Symposium on Algorithms and Computation, ISAAC'98
CountryKorea, Republic of
CityTaejon
Period98-12-1498-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

    Hsieh, S-Y., Ho, C. W., Hsu, T. S., Ko, M. T., & Chen, G. H. (1998). Characterization of efficiently solvable problems on distance-hereditary graphs. In 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).