Dynamic programming on distance-hereditary graph

Maw Shang Chang, Sun Yuan Hsieh, Gen Huey Chen

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

47 Citations (Scopus)

Abstract

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
Pages344-353
Number of pages10
ISBN (Print)3540638903, 9783540638902
DOIs
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)
Volume1350
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th Annual International Symposium on Algorithms and Computation, ISAAC 1997
CountrySingapore
CitySingapore
Period97-12-1797-12-19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this