Minimum Connected Dominating Set and Backbone of a Random Graph

Yusupjan Habibulla, Hai-Jun Zhou

We study the minimum dominating set problem as a representative combinatorial optimization challenge with a global topological constraint. The requirement that the backbone induced…