A Game Theoretic Approach For Dominating Set Problems

Covering problems are classic combinatorial optimization problems,which have wide applications in the real world,such as monitoring environment using dominating set.In this thesis,two variants of the dominating set problem are studied using game theory:connected dominating set problem and secure dominating set problem.The connected dominating set problem is motivated by the requirement of infor-mation sharing among wireless sensors in a network monitoring system.For a graph G=(V,E),for(?)vertex v?V\C,if(?)u?Ni?C,then C is a dominating set where Ni is the neighbor set of vi.Furthermore,if G[C]is connected,then C is connected dominating set(CDS).The secure dominating set problem is motivated by the demand for security of dy-namic network monitoring system.For a graph G=(V,E),suppose C is a dominating set of G,if for each vertex u? V\C,there is a vertex v?C such that uv?E and(C\{v})? {u} is also a dominating set of G,then C is a secure dominating set(SDS).This paper consists of four chapters.In the first chapter,we introduce basic no-tations,backgrounds and research status of CDS and SDS.In the second chapter,we propose a game theoretic approach to find a CDS,and prove that starting from any non-trivial initial state,every non-trivial Nash equilibrium is a minimal CDS,and reaching a non-trivial Nash equilibrium needs O(n)rounds in the worst case.In the third chapter,we study the secure dominating set problem(SDS)in a mult,i-agent system.We propose a secure domination game;show that every Nash equilibrium is a minimal SDS,which is also a Pareto-optimal solution;prove that the proposed game is an exact potential game;and design a polynomial-time distributed local algorithm for SDS which converges to a Nash equilibrium in O(n)rounds of interactions;extensive experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.In the forth chapter,we make a discussion and conclusion of our results and methods.