A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a...A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.展开更多
We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result a...We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].展开更多
To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints i...To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints is proposed. Based on the （α, β）-tree concept, a new connected dominating tree with bounded transmission delay problem（CDTT） is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases： The first phase constructs a maximum independent set（MIS）in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with（ α,β）-constraints balancing the requirements of power consumption and transmission delay.展开更多
For an arbitrary subset P of the reals, a function f ： V →P is defined to be a P-dominating function of a graph G = （V, E） if the sum of its function values over any closed neighbourhood is at least 1. That is, fo...For an arbitrary subset P of the reals, a function f ： V →P is defined to be a P-dominating function of a graph G = （V, E） if the sum of its function values over any closed neighbourhood is at least 1. That is, for every v ∈ V, f（N[v]） ≥ 1. The definition of total P-dominating function is obtained by simply changing ‘closed＇ neighborhood N[v] in the definition of P-dominating function to ‘open＇ neighborhood N（v）. The （total） P-domination number of a graph G is defined to be the infimum of weight w（f） = ∑v ∈ V f（v） taken over all （total） P-dominating function f. Similarly, the P-edge and P-star dominating functions can be defined. In this paper we survey some recent progress on the topic of dominating functions in graph theory. Especially, we are interested in P-, P-edge and P-star dominating functions of graphs with integer values.展开更多
Weiyuan shale gas play is characterized by thin high-quality reservoir thickness,big horizontal stress difference,and big productivity differences between wells.Based on integrated evaluation of shale gas reservoir ge...Weiyuan shale gas play is characterized by thin high-quality reservoir thickness,big horizontal stress difference,and big productivity differences between wells.Based on integrated evaluation of shale gas reservoir geology and well logging interpretation of more than 20 appraisal wells,a correlation was built between the single well test production rate and the high-quality reservoir length drilled in the horizontal wells,high-quality reservoir thickness and the stimulation treatment parameters in over 100 horizontal wells,the dominating factors on horizontal well productivity were found out,and optimized development strategies were proposed.The results show that the deployed reserves of high-quality reservoir are the dominating factors on horizontal well productivity.In other words,the shale gas well productivity is controlled by the thickness of the high-quality reservoir,the high-quality reservoir drilling length and the effectiveness of stimulation.Based on the above understanding,the development strategies in Weiyuan shale gas play are optimized as follows:(1)The target of horizontal wells is located in the middle and lower parts of Longyi 11(Wei202 area)and Longyi 11(Wei204 area).(2)Producing wells are drilled in priority in the surrounding areas of Weiyuan county with thick high-quality reservoir.(3)A medium to high intensity stimulation is adopted.After the implementation of these strategies,both the production rate and the estimated ultimate recovery(EUR)of individual shale gas wells have increased substantially.展开更多
The minimal dominating set for a digraph(directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution fo...The minimal dominating set for a digraph(directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erds-Rnyi graphs to find the ground state energy. In this paper we continue to develope the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following.(i) The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one.(ii) We determine the ground state energy and the transition point of the Erd?os-R′enyi random graph.(iii) The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm.展开更多
A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which i...A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.展开更多
In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking me...In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking method based on dominating number is proposed to build the Pareto front. Without increasing basic Pareto method’s computation complexity and introducing new parameters, a new multiobjective genetic algorithm based on proposed ranking method (MOGA-DN) is presented. Simulation results on function optimization and parameters optimization of control system verify the efficiency of MOGA-DN.展开更多
In order to construct and maintain stability Connected Dominating Set over MANET in Ubiquitous Stub Network, this paper proposes a novel area-based CDS construction and maintenance algorithm. The algorithm is divided ...In order to construct and maintain stability Connected Dominating Set over MANET in Ubiquitous Stub Network, this paper proposes a novel area-based CDS construction and maintenance algorithm. The algorithm is divided into three phases: 1) Area Partition; 2) Area Expansion; 3) Area Connection. In additional, maintenance strategy is proposed in each phase respectively to handle node mobility with timer. At last, the simulation is implemented with OPNET and MATLAB and the results are analyzed in detailed with Size of CDS, Message Overhead and other indexes.展开更多
This paper proposes a connected dominating set (CDS) based mobility management algorithm, CMMA, to solve the problems of node entering, exiting and movement in mobile ad hoc networks (MANETs), which ensures the connec...This paper proposes a connected dominating set (CDS) based mobility management algorithm, CMMA, to solve the problems of node entering, exiting and movement in mobile ad hoc networks (MANETs), which ensures the connectivity and efficiency of the CDS. Compared with Wu's algorithm, the proposed algorithm can make full use of present network conditions and involves fewer nodes. Also it has better performance with regard to the approximation factor, message complexity, and time complexity.展开更多
The directed L-distance minimal dominating set(MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theo...The directed L-distance minimal dominating set(MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi(ER)random graph and regular random(RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation(BP) algorithm does not converge when the inverse temperatureβ exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds3.3;there is no entropy transition point(or β = ■) in other circumstances. Third, the results of the replica symmetry(RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm.展开更多
The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless networks.In this paper,we apply algorithmic game theory to study the minimum secure dominating se...The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless networks.In this paper,we apply algorithmic game theory to study the minimum secure dominating set(Min SDS) problem in a multi-agent system.We design a game framework for SDS and show that every Nash equilibrium(NE) is a minimal SDS,which is also a Pareto-optimal solution.We prove that the proposed game is an exact potential game,and thus NE exists,and design a polynomial-time distributed local algorithm which converges to an NE in O(n) rounds of interactions.Extensive experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.展开更多
Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum a...Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.展开更多
This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Consider...This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Considering that the hosts in mobile networks have different characteristics, this paper proposes a method of calculating minimal dominating set with weight. The nodes can be chosen to form a minimal dominating set when the network topology changes. For the host switch on/off operation, the updating algorithm was provided. The change in the status of a hostaffects only the status of hosts in the restricted vicinity. Simulation results show that the proposed method can ensure fewer dominators but with higher weight to form the minimal dominating set and the nodes can be adaptive to the changes of network topology.展开更多
The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set proble...The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.展开更多
基金Ming Chen was supported by National Key Research and Development Program of China(No.2024YFA1013900)。
文摘A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.
文摘We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].
基金Major Program of the National Natural Science Foundation of China (No.70533050)High Technology Research Program ofJiangsu Province(No.BG2007012)+1 种基金China Postdoctoral Science Foundation(No.20070411065)Science Foundation of China University of Mining andTechnology(No.OC080303)
文摘To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints is proposed. Based on the （α, β）-tree concept, a new connected dominating tree with bounded transmission delay problem（CDTT） is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases： The first phase constructs a maximum independent set（MIS）in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with（ α,β）-constraints balancing the requirements of power consumption and transmission delay.
基金Project supported by the National Natural Science Foundation of China （Grant No.10571117）, the Shuguang Plan of Shang- hai Education Devel0pment Foundation （Grant No.06SG42）, and the Natural Science Development Foundation of Shanghai Municipal Commission of Education （Grant No.05AZ04）
文摘For an arbitrary subset P of the reals, a function f ： V →P is defined to be a P-dominating function of a graph G = （V, E） if the sum of its function values over any closed neighbourhood is at least 1. That is, for every v ∈ V, f（N[v]） ≥ 1. The definition of total P-dominating function is obtained by simply changing ‘closed＇ neighborhood N[v] in the definition of P-dominating function to ‘open＇ neighborhood N（v）. The （total） P-domination number of a graph G is defined to be the infimum of weight w（f） = ∑v ∈ V f（v） taken over all （total） P-dominating function f. Similarly, the P-edge and P-star dominating functions can be defined. In this paper we survey some recent progress on the topic of dominating functions in graph theory. Especially, we are interested in P-, P-edge and P-star dominating functions of graphs with integer values.
文摘Weiyuan shale gas play is characterized by thin high-quality reservoir thickness,big horizontal stress difference,and big productivity differences between wells.Based on integrated evaluation of shale gas reservoir geology and well logging interpretation of more than 20 appraisal wells,a correlation was built between the single well test production rate and the high-quality reservoir length drilled in the horizontal wells,high-quality reservoir thickness and the stimulation treatment parameters in over 100 horizontal wells,the dominating factors on horizontal well productivity were found out,and optimized development strategies were proposed.The results show that the deployed reserves of high-quality reservoir are the dominating factors on horizontal well productivity.In other words,the shale gas well productivity is controlled by the thickness of the high-quality reservoir,the high-quality reservoir drilling length and the effectiveness of stimulation.Based on the above understanding,the development strategies in Weiyuan shale gas play are optimized as follows:(1)The target of horizontal wells is located in the middle and lower parts of Longyi 11(Wei202 area)and Longyi 11(Wei204 area).(2)Producing wells are drilled in priority in the surrounding areas of Weiyuan county with thick high-quality reservoir.(3)A medium to high intensity stimulation is adopted.After the implementation of these strategies,both the production rate and the estimated ultimate recovery(EUR)of individual shale gas wells have increased substantially.
基金Supported by the Doctoral Startup Fund of Xinjiang University of China under Grant No.208-61357the National Natural Science Foundation of China under Grant No.11765021
文摘The minimal dominating set for a digraph(directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erds-Rnyi graphs to find the ground state energy. In this paper we continue to develope the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following.(i) The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one.(ii) We determine the ground state energy and the transition point of the Erd?os-R′enyi random graph.(iii) The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm.
文摘A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.
基金supported by the Academic Outstanding Youth Talented Person Fund of Anhui Province (No.2009SQR2014)
文摘In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking method based on dominating number is proposed to build the Pareto front. Without increasing basic Pareto method’s computation complexity and introducing new parameters, a new multiobjective genetic algorithm based on proposed ranking method (MOGA-DN) is presented. Simulation results on function optimization and parameters optimization of control system verify the efficiency of MOGA-DN.
基金supported by the National Science and Technology Support Program of China (2015BAG10B01)the Science and Technology Project of State Grid Corporation of China (SGIT0000KJJS1500008)
文摘In order to construct and maintain stability Connected Dominating Set over MANET in Ubiquitous Stub Network, this paper proposes a novel area-based CDS construction and maintenance algorithm. The algorithm is divided into three phases: 1) Area Partition; 2) Area Expansion; 3) Area Connection. In additional, maintenance strategy is proposed in each phase respectively to handle node mobility with timer. At last, the simulation is implemented with OPNET and MATLAB and the results are analyzed in detailed with Size of CDS, Message Overhead and other indexes.
文摘This paper proposes a connected dominating set (CDS) based mobility management algorithm, CMMA, to solve the problems of node entering, exiting and movement in mobile ad hoc networks (MANETs), which ensures the connectivity and efficiency of the CDS. Compared with Wu's algorithm, the proposed algorithm can make full use of present network conditions and involves fewer nodes. Also it has better performance with regard to the approximation factor, message complexity, and time complexity.
基金supported by the doctoral startup fund of Xinjiang University of China (grant number 208-61357)the National Natural Science Foundation of China (grant number 11 465 019,11 664 040)。
文摘The directed L-distance minimal dominating set(MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi(ER)random graph and regular random(RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation(BP) algorithm does not converge when the inverse temperatureβ exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds3.3;there is no entropy transition point(or β = ■) in other circumstances. Third, the results of the replica symmetry(RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm.
基金supported in part by the National Natural Science Foundation of China(U20A2068, 11771013)Zhejiang Provincial Natural Science Foundation of China (LD19A010001)。
文摘The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless networks.In this paper,we apply algorithmic game theory to study the minimum secure dominating set(Min SDS) problem in a multi-agent system.We design a game framework for SDS and show that every Nash equilibrium(NE) is a minimal SDS,which is also a Pareto-optimal solution.We prove that the proposed game is an exact potential game,and thus NE exists,and design a polynomial-time distributed local algorithm which converges to an NE in O(n) rounds of interactions.Extensive experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.
基金Project supported by the National Natural Science Foundation of China(Grant No.62101600)the Science Foundation of China University of Petroleum,Beijing(Grant No.2462021YJRC008)the State Key Laboratory of Cryptology(Grant No.MMKFKT202109).
文摘Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.
基金Supported by National Natural Science Foundation of China (No.60973141)Natural Science Foundation of Tianjin (No.09JCYBJC00300)
文摘This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Considering that the hosts in mobile networks have different characteristics, this paper proposes a method of calculating minimal dominating set with weight. The nodes can be chosen to form a minimal dominating set when the network topology changes. For the host switch on/off operation, the updating algorithm was provided. The change in the status of a hostaffects only the status of hosts in the restricted vicinity. Simulation results show that the proposed method can ensure fewer dominators but with higher weight to form the minimal dominating set and the nodes can be adaptive to the changes of network topology.
文摘The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.
