Dynamic programming on distance-hereditary graph

Maw Shang Chang, Sun Yuan Hsieh, Gen Huey Chen

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

53 Citations (Scopus)


In this paper, we define a one-vertex-extension tree for a distance-hereditary graph and show how to build it. We then give a unified approach to designing efficient dynamic programming algorithms for distance-hereditary graphs based upon the one-vertex-extension tree. We give linear time algorithms for the weighted vertex cover and weighted independent domination problems and give an 0(n2) time algorithm to compute a minimum fill-in and the treewidth for a distance-hereditary graph.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 8th International Symposium, ISAAC 1997, Proceedings
EditorsHon Wai Leong, Sanjay Jain, Hiroshi Imai
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540638903, 9783540638902
Publication statusPublished - 1997
Event8th Annual International Symposium on Algorithms and Computation, ISAAC 1997 - Singapore, Singapore
Duration: 1997 Dec 171997 Dec 19

Publication series

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


Other8th Annual International Symposium on Algorithms and Computation, ISAAC 1997

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Dynamic programming on distance-hereditary graph'. Together they form a unique fingerprint.

Cite this