On domination number of Cartesian product of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C₂□Cn)=n; γ(C₃□Cn)=n if , otherwise, γ(C₃□Cn)=n+1; if , otherwise, .     

Bounded-distance multi-clusterhead formation in wireless ad hoc networks

We present a clustering technique addressing redundancy for bounded-distance clusters, which means being able to determine the minimum number of cluster-heads per node, and the maximum distance from nodes to their cluster-heads. This problem is similar to computing a (k, r)-dominating set, (k, r)-DS, of the network. (k, r)-DS is defined as the problem of selecting a minimum cardinality vertex set D of the network such that every vertex u not in D is at a distance smaller than or equal to r from at least k vertices in D. In mobile ad hoc networks (MANETs), clusters should be computed distributively, because the topology may change frequently. We present the first centralized and distributed solutions to the (k, r)-DS problem for arbitrary topologies. The centralized algorithm computes a (k · ln Δ)-approximation, where Δ is the largest cardinality among all r-hop neighborhoods in the network. The distributed approach is extended for clustering applications, while the centralized is used as a lower bound for comparison purposes. Extensive simulations are used to compare the distributed solution with the centralized one. As a case study, we propose a novel multi-core multicast protocol that applies the distributed solution for the election of cores. The new protocol is compared against PUMA, one of the best performing multicast protocols for MANETS. Simulation results show that the new protocol outperforms PUMA on the context of static networks.     

一类非线性时滞系统的自适应模糊反向递推控制

针对一类含有未知函数的非线性时滞系统，提出了一种自适应模糊跟踪控制器的设计方案。在自适应反向递推设计方法的基础上，采用模糊逻辑系统在线辨识非线性未知函数，采用自适应边界技术估计辨识误差上界。Domination方法和构造合适的Lyapunov-Krasovskii泛函相结合抵消了非线性时滞项对系统的影响。证明了闭环系统为半全局一致最终有界，通过调节设计参数可以实现任意的跟踪精度。实例仿真说明了方案的可行性。     

Dynamic deployment optimization of near space communication system using a novel estimation of distribution algorithm

A robust deployment of the airship platforms is crucial to the performance of the Near Space Communication System (NSCS) in the dynamic environment. In this paper, a multiobjective NSCS deployment optimization model with multi-phased periodic user distribution is proposed. To optimize this model, we propose a local incremental estimation of distribution algorithm with an asymmetrical domination relationship within the multiobjective evolutionary algorithm based on decomposition framework. The conflict between the selection mechanism and the domination relationship is also analyzed theoretically for the first time. To obtain robust solutions under this conflict, the local distribution information of a certain subproblem within several generations is encompassed into a local incremental distribution model. As a generalized form of the existing domination relationship, an asymmetrical domination relationship (ADR), which treats the current and past objective values differently, is proposed to select robust solutions. The proposed algorithm is also tested on four designed problems compared with another four popular algorithms and proves its superiority. Some important parameters are also investigated in the experiments and some guidelines on tuning these parameters are given as well.     

无线传感器网络延迟约束的MDC分布式轨道规划算法

针对引入移动元素后无线传感器网络数据面临的收集延时问题,提出了一种分布式的移动数据收集器(MDC)轨道规划算法.首先给出基于k跳支配集的MDC最小时延规划问题定义,并证明它是NP-hard.在基于集结的数据收集模式汇总,k跳支配节点作为集结点缓存传感节点收集的数据并在MDC到达时上传.然后,提出了一种高效的基于k跳支配集的MDC轨迹构建算法.算法通过分布式的k-跳支配集算法找出网络中的支配节点,进而通过Prim算法和Christofides近似算法对MDC的移动轨道进行规划.算法的正确性、k-跳支配集的界、时间复杂性和消息交换复杂性通过理论进行分析.最后,通过仿真实验验证了算法的有效性.仿真结论表明,与同类算法相比,所提出算法能够显著缩短MDC的移动轨迹,因而可以降低网络延迟.     

输电跨越塔基础承台大体积砼温度与裂缝控制

本文从大体积混凝土的温度应力影响因素、温度控制措施 (原材料、入模温度、施工工艺、混凝土的保温等 )、热工计算、温度监控等方面总结、介绍了大体积混凝土的温度与裂缝控制 ,可为同类工程借鉴和参考     

A survey on self-stabilizing algorithms for independence,domination, coloring,and matching in graphs

Dijkstra defined a distributed system to be self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in a finite time. Even though the concept of self-stabilization received little attention when it was introduced, it has become one of the most popular fault tolerance approaches. On the other hand, graph algorithms form the basis of many network protocols. They are used in routing, clustering, multicasting and many other tasks. The objective of this paper is to survey the self-stabilizing algorithms for dominating and independent set problems, colorings, and matchings. These graph theoretic problems are well studied in the context of self-stabilization and a large number of algorithms have been proposed for them.     

TSP Heuristics: Domination Analysis and Complexity

   Abstract. We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph K _n produce a solution no worse than the average cost of a tour in K _n in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon, Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.