Weighted connected domination and Steiner trees in distance-hereditary graphs

Hong Gwa Yeh, Gerard J. Chang

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

Distance-hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. This paper studies distance-hereditary graphs from an algorithmic viewpoint. In particular, we present linear-time algorithms for finding a minimum weighted connected dominating set and a minimum vertex-weighted Steiner tree in a distance-hereditary graph. Both problems are script N sign ℘-complete in general graphs.

Original languageEnglish
Pages (from-to)245-253
Number of pages9
JournalDiscrete Applied Mathematics
Volume87
Issue number1-3
DOIs
StatePublished - 5 Oct 1998

Keywords

  • Algorithm
  • Cograph
  • Connected domination
  • Distance-hereditary graph
  • Steiner tree

Fingerprint

Dive into the research topics of 'Weighted connected domination and Steiner trees in distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this