Dynamic Programming on Distance-Hereditary Graphs.
Journal
Algorithms and Computation, 8th International Symposium, ISAAC '97, Singapore, December 17-19, 1997, Proceedings
Pages
344-353
Date Issued
1997
Author(s)
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.
Type
conference paper