http://scholars.ntou.edu.tw/handle/123456789/19134
標題: | A linear-time algorithm for weighted paired-domination on block graphs | 作者: | Lin, Ching-Chi Hsieh, Cheng-Yu Mu, Ta-Yu |
關鍵字: | Weighted paired-domination;Perfect matching;Block graph;Dynamic programming | 公開日期: | 22-十一月-2021 | 出版社: | SPRINGER | 來源出版物: | JOURNAL OF COMBINATORIAL OPTIMIZATION | 摘要: | In a graph G = (V, E), a set S subset of V(G) is said to be a dominating set of G if every vertex not in S is adjacent to a vertex in S. Let G[S] denote the subgraph of G induced by a subset S of V (G). A dominating set S of G is called a paired-dominating set of G if the induced subgraph G[S] contains a perfect matching. Suppose that, for each v is an element of V(G), we have a weight w(v) specifying the cost for adding v to S. The weighted paired-domination problem is to find a paired-dominating set S whose total weights w(S) = (Sigma nu is an element of s )w(v) is minimized. In this paper, we propose an O (n + m)-time algorithm for the weighted paired-domination problem on block graphs using dynamic programming, which strengthens the results in [Theoret Comput Sci 410(47-49):5063-5071, 2009] and [J Comb Optim 19(4):457-470, 2010]. Moreover, the algorithm can be completed in O(n) time if the block-cut-vertex structure of G is given. |
URI: | http://scholars.ntou.edu.tw/handle/123456789/19134 | ISSN: | 1382-6905 | DOI: | 10.1007/s10878-021-00767-5 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。