Approximation for Dominating Set Problem with Measure Functions

Ning Chen; Jie Meng; Jiawei Rong; Hong Zhu

Approximation for Dominating Set Problem with Measure Functions

Authors

Ning Chen
Jie Meng
Jiawei Rong
Hong Zhu

Keywords:

Dominating set, complexity, approximation, inapproximability

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2012-02-06

How to Cite

Chen, N., Meng, J., Rong, J., & Zhu, H. (2012). Approximation for Dominating Set Problem with Measure Functions. COMPUTING AND INFORMATICS, 23(1), 37–49. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/407