標題: Weighted connected domination and Steiner trees in distance-hereditary graphs
作者: Yeh, HG
Chang, GJ
應用數學系
Department of Applied Mathematics
關鍵字: distance-hereditary graph;connected domination;Steiner tree;algorithm;cograph
公開日期: 5-十月-1998
摘要: 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 NP-complete in general graphs. (C) 1998 Elsevier Science B.V. All rights reserved.
URI: http://hdl.handle.net/11536/31818
ISSN: 0166-218X
期刊: DISCRETE APPLIED MATHEMATICS
Volume: 87
Issue: 1-3
起始頁: 245
結束頁: 253
顯示於類別:期刊論文


文件中的檔案:

  1. 000076462200018.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。