|
Abstract
|
It is a well-known fact that finding a minimum dominating set and consequently finding the
domination number of a general graph is an NP-complete problem. Here, we first model this
problem as nonlinear binary optimization problems and then extract two closely related
semidefinite relaxations. For each of these relaxations, different rounding algorithms are exploited
to produce near-optimal dominating sets. Feasibility of the generated solutions and efficiency of
the algorithms are analyzed.
|