عنوان
|
Semidefinite relaxation technique for approximating the k-tuple domination number
|
نوع پژوهش
|
مقاله ارائه شده کنفرانسی
|
کلیدواژهها
|
Semidefinite programming, Dominating set, $k$-tuple dominating set
|
چکیده
|
It is a well-known fact that finding a minimum dominating set and consequently finding the $k$-tuple dominating set of a general graph is an NP-complete problem. In this paper, we first model these problems as nonlinear binary optimization problems and then extract two semidefinite relaxations.
|
پژوهشگران
|
مهدی جهانگیری (نفر اول)
|