The Roman domination problem is an important combinatorial optimization problem that is derived from an old story of defending the Roman Empire and now regains new significance in cyber space security,considering back...The Roman domination problem is an important combinatorial optimization problem that is derived from an old story of defending the Roman Empire and now regains new significance in cyber space security,considering backups in the face of a dynamic network security requirement.In this paper,firstly,we propose a Roman domination game(RDG)and prove that every Nash equilibrium(NE)of the game corresponds to a strong minimal Roman dominating function(S-RDF),as well as a Pareto-optimal solution.Secondly,we show that RDG is an exact potential game,which guarantees the existence of an NE.Thirdly,we design a game-based synchronous algorithm(GSA),which can be implemented distributively and converge to an NE in O(n)rounds,where n is the number of vertices.In GSA,all players make decisions depending on local information.Furthermore,we enhance GSA to be enhanced GSA(EGSA),which converges to a better NE in O(n2)rounds.Finally,we present numerical simulations to demonstrate that EGSA can obtain a better approximate solution in promising computation time compared with state-of-the-art algorithms.展开更多
A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weig...A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weight of a Roman dominating function is the value f（V） = Σu∈Vf（u）. The minimum weight of a Roman dominating function on a graph G, denoted by γR（G）, is called the Roman dominating number of G. In this paper, we will characterize a tree T with γR（T） = γ（T） ＋ 3.展开更多
For a graph G=(V,E),a Roman{2}-dominating function f:V→{0,1,2}has the property that for every vertex v∈V with f(v)=0,either v is adjacent to at least one vertex u for which f(u)=2,or at least two vertices u1 and u2 ...For a graph G=(V,E),a Roman{2}-dominating function f:V→{0,1,2}has the property that for every vertex v∈V with f(v)=0,either v is adjacent to at least one vertex u for which f(u)=2,or at least two vertices u1 and u2 for which f(u1)=f(u2)=1.A Roman{2}-dominating function f=(V0,V1,V2)is called independent if V1∪V2 is an independent set.The weight of an independent Roman{2}-dominating function f is the valueω(f)=Σv∈V f(v),and the independent Roman{2}-domination number i{R2}(G)is the minimum weight of an independent Roman{2}-dominating function on G.In this paper,we characterize all trees with i{R2}(T)=γ(T)+1,and give a linear time algorithm to compute the value of i{R2}(T)for any tree T.展开更多
基金supported in part by the National Natural Science Foundation of China(U20A2068)Zhejiang Provincial Natural Science Foundation of China(LD19A010001,LZ24F030009).
文摘The Roman domination problem is an important combinatorial optimization problem that is derived from an old story of defending the Roman Empire and now regains new significance in cyber space security,considering backups in the face of a dynamic network security requirement.In this paper,firstly,we propose a Roman domination game(RDG)and prove that every Nash equilibrium(NE)of the game corresponds to a strong minimal Roman dominating function(S-RDF),as well as a Pareto-optimal solution.Secondly,we show that RDG is an exact potential game,which guarantees the existence of an NE.Thirdly,we design a game-based synchronous algorithm(GSA),which can be implemented distributively and converge to an NE in O(n)rounds,where n is the number of vertices.In GSA,all players make decisions depending on local information.Furthermore,we enhance GSA to be enhanced GSA(EGSA),which converges to a better NE in O(n2)rounds.Finally,we present numerical simulations to demonstrate that EGSA can obtain a better approximate solution in promising computation time compared with state-of-the-art algorithms.
基金Supported by the NSF of education Department of Henan Province(200510475038)
文摘A Roman dominating function on a graph G = （V, E） is a function f ： V→{0, 1, 2} satisfying the condition that every vertex u for which f（u） = 0 is adjacent to at least one vertex v for which f（v） = 2. The weight of a Roman dominating function is the value f（V） = Σu∈Vf（u）. The minimum weight of a Roman dominating function on a graph G, denoted by γR（G）, is called the Roman dominating number of G. In this paper, we will characterize a tree T with γR（T） = γ（T） ＋ 3.
基金Supported by National Natural Science Foundation of China(Grant No.12171440)。
文摘For a graph G=(V,E),a Roman{2}-dominating function f:V→{0,1,2}has the property that for every vertex v∈V with f(v)=0,either v is adjacent to at least one vertex u for which f(u)=2,or at least two vertices u1 and u2 for which f(u1)=f(u2)=1.A Roman{2}-dominating function f=(V0,V1,V2)is called independent if V1∪V2 is an independent set.The weight of an independent Roman{2}-dominating function f is the valueω(f)=Σv∈V f(v),and the independent Roman{2}-domination number i{R2}(G)is the minimum weight of an independent Roman{2}-dominating function on G.In this paper,we characterize all trees with i{R2}(T)=γ(T)+1,and give a linear time algorithm to compute the value of i{R2}(T)for any tree T.
