Distributing codes to specific target sensors in order to fix bugs and/or install a new application is an important management task in WSNs (Wireless Sensor Networks). For the energy efficient dissemination of such codes to specific target sensors, it is required to select the minimum required number of forwarders with the fewest control messages. In this paper, we propose a novel RPL (Routing Protocol for Low-power and lossy networks)-based tree construction scheme for target-specific code dissemination, which is called R-TCS. The main idea of R-TCS is that by leveraging the data collection tree created by a standard routing protocol RPL, it is possible to construct the code dissemination tree with the minimum numbers of non-target sensors and control messages. Since by creating a data collection tree each sensor exchanges RPL messages with the root of the tree, every sensor knows which sensors compose its upwards route, i.e. the route towards the root, and downwards route, i.e. the route towards the leaves. Because of these properties, a target sensor can select the upward route that contains the minimum number of non-target sensors. In addition, a sensor whose downward routes do not contain a target sensor is not required to transmit redundant control messages which are related to the code dissemination operation. In this way, R-TCS can reduce the energy consumption which typically happens in other target-specific code dissemination schemes by the transmission of control messages. In fact, various performance evaluation results obtained by means of computer simulations show that R-TCS reduces by at least 50% energy consumption as compared to the other previous known target-specific code dissemination scheme under the condition where ratio of target sensors is 10% of all sensors.

Given an undirected graph G, an edge dominating set is a subset F of edges such that each edge not in F is adjacent to some edge in F, and computing the minimum size of an edge dominating set is known to be NP-hard. Since the size of any edge dominating set is at least half of the maximum size µ(G) of a matching in G, we study the problem of testing whether a given graph G has an edge dominating set of size ⌈µ(G)/2⌉ or not. In this paper, we prove that the problem is NP-complete, whereas we design an O*(2.0801µ(G)/2)-time and polynomial-space algorithm to the problem.

A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n3) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.

An orthogonal ray graph is an intersection graph of horizontal and vertical rays (closed half-lines) in the plane. Such a graph is 3-directional if every vertical ray has the same direction, and 2-directional if every vertical ray has the same direction and every horizontal ray has the same direction. We derive some structural properties of orthogonal ray graphs, and based on these properties, we introduce polynomial-time algorithms that solve the dominating set problem, the induced matching problem, and the strong edge coloring problem for these graphs. We show that for 2-directional orthogonal ray graphs, the dominating set problem can be solved in O(n2 log5 n) time, the weighted dominating set problem can be solved in O(n4 log n) time, and the number of dominating sets of a fixed size can be computed in O(n6 log n) time, where n is the number of vertices in the graph. We also show that for 2-directional orthogonal ray graphs, the weighted induced matching problem and the strong edge coloring problem can be solved in O(n2+m log n) time, where m is the number of edges in the graph. Moreover, we show that for 3-directional orthogonal ray graphs, the induced matching problem can be solved in O(m2) time, the weighted induced matching problem can be solved in O(m4) time, and the strong edge coloring problem can be solved in O(m3) time. We finally show that the weighted induced matching problem can be solved in O(m6) time for orthogonal ray graphs.

Given a graph G = (V,E) together with a nonnegative integer requirement on vertices r:V Z+, the annotated edge dominating set problem is to find a minimum set M ⊆ E such that, each edge in E - M is adjacent to some edge in M, and M contains at least r(v) edges incident on each vertex v ∈ V. The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721n) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306k)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an annotated edge dominating set of size k or not.

This letter proposes a novel connected dominanting set based decentralized cooperative spectrum sensing algorithm for cognitive radio networks. It is analytically shown that the proposed algorithm distributively converges to the average consensus as that of traditional distributed consensus algorithm, while reducing both the convergence time and message complexity significantly.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate a self-stabilizing distributed approximation for the minimum k-dominating set (KDS) problem in general networks. The minimum KDS problem is a generalization of the well-known dominating set problem in graph theory. For a graph G = (V,E), a set Dk V is a KDS of G if and only if each vertex not in Dk is adjacent to at least k vertices in Dk. The approximation ratio of our algorithm is , where Δ is the maximum degree of G, in the networks of which the minimum degree is more than or equal to k.

We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance k1 of at least one resource copy, which is called the k-bounded placement problem. The structure of a distributed computing system is represented by a graph. The k-bounded placement problem is first transformed into the problem of finding smallest k-dominating sets in a graph. Searching for smallest k-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known A* algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.