Actors'relocation is utilized during the network initialization to enhance real-time performance of wireless sensor and actor networks(WSANs)which is an important issue of WSANs.The actor deployment problem in WSA...Actors'relocation is utilized during the network initialization to enhance real-time performance of wireless sensor and actor networks(WSANs)which is an important issue of WSANs.The actor deployment problem in WSANs is proved NP-Hard whether the amount of actors is redundant or not,but to the best of our knowledge,no effective distributed algorithms in previous research can solve the problem.Thus two actor deployment strategies which need not the boundary control compared with present deployment strategies are proposed to solve this problem approximately based on the Voronoi diagram.Through simulation experiment,the results show that our distributed strategies are more effective than the present deployment strategies in terms of real-time performance,convergence time and energy consumption.展开更多
A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider...A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.展开更多
In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and ...In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and show that for a kind of graphs whose adjacent matrices are balanced, the existence of universal minimal total dominating functions coincides with that of 0-1 ones. It is also proved that for general graphs, the problem of testing the existence of 0-1 universal minimal total dominating functions is NP-hard.展开更多
基金Supported by the National Natural Science Foundation of China(No.60803148,60973124)
文摘Actors'relocation is utilized during the network initialization to enhance real-time performance of wireless sensor and actor networks(WSANs)which is an important issue of WSANs.The actor deployment problem in WSANs is proved NP-Hard whether the amount of actors is redundant or not,but to the best of our knowledge,no effective distributed algorithms in previous research can solve the problem.Thus two actor deployment strategies which need not the boundary control compared with present deployment strategies are proposed to solve this problem approximately based on the Voronoi diagram.Through simulation experiment,the results show that our distributed strategies are more effective than the present deployment strategies in terms of real-time performance,convergence time and energy consumption.
基金supported by the Minister of Science and Higher Education of Poland (Grant No. JP2010009070)
文摘A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.
基金This research is supported by the National Natural Science Foundation of China (No. 10371114).
文摘In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and show that for a kind of graphs whose adjacent matrices are balanced, the existence of universal minimal total dominating functions coincides with that of 0-1 ones. It is also proved that for general graphs, the problem of testing the existence of 0-1 universal minimal total dominating functions is NP-hard.
