Weighted connected domination and Steiner trees in distance-hereditary graphs

Hong Gwa Yeh, Gerard J. Chang

研究成果: 雜誌貢獻期刊論文同行評審

19 引文 斯高帕斯(Scopus)

摘要

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.

原文???core.languages.en_GB???
頁(從 - 到)245-253
頁數9
期刊Discrete Applied Mathematics
87
發行號1-3
DOIs
出版狀態已出版 - 5 10月 1998

指紋

深入研究「Weighted connected domination and Steiner trees in distance-hereditary graphs」主題。共同形成了獨特的指紋。

引用此