Approximation for dominating set problem with measure functions

被引：0

作者：

Chen, N ^{[1
]}

Meng, J ^{[1
]}

Rong, J ^{[1
]}

Zhu, H ^{[1
]}

机构：

[1] Fudan Univ, Dept Comp Sci, Shanghai, Peoples R China

来源：

COMPUTING AND INFORMATICS | 2004年 / 23卷 / 01期

关键词：

dominating set; complexity; approximation; inapproximability;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, we study the Dominating Set problem with measure functions, which is extended from the general Dominating Set problem. We study the correspondnig problems on complexity, approximation and inapproximability for Dominating Set problem with measure functions. In addition, we extend our results to the weighted graphs.

引用

页码：37 / 49

页数：13