Virtual backbone formation algorithm based on GBG for wireless sensor networks by SUN Yan-jing, QIAN Jian-sheng

“…This approach constructs an maximal independent set （MIS） by network decomposition scheme and a clustergraph by coloring, computes local mini- mum dominating sets in 2-separated collection of subnets to form a global optimal solution which is used to directly con- struct an approximation minimum connected dominating sets by adjusting transmission range of clusterheads and finally use marking process and self-pruning to reduce the virtual backbone, without additional gateways. …”
Get full text

Strongly connected dominating set construction algorithm balancing time delay and energy consumption by Yan-jing SUN, Jian-sheng QIAN, Shan-shan MA, Peng REN

“…To the asymmetry of link in wireless sensor networks,a problem about the strongly connected dominating tree with bounded transmission delay (SDTT) was put forward.The distributed strongly connected dominating tree (SCDT) algorithm was also proposed to construct strongly connected dominating set balancing transmission delay and energy consumption.Firstly,it constructed a maximal independent set (MIS) based on a unit disk graph,and then implemented the SCDT algorithm based on a double weighted and directed graph fulfilling the requirements of energy consumption and transmission delays simultaneously.The theoretical analysis and simulation results show that the presented algorithm can correctly solve the SDTT problem and construct the connected dominating sets(CDS)with constraints to form virtual backbone.…”
Get full text

Impossibility Results for Byzantine-Tolerant State Observation, Synchronization, and Graph Computation Problems by Ajay D. Kshemkalyani, Anshuman Misra

“…These problems are the following: mutual exclusion, global snapshot recording, termination detection, deadlock detection, predicate detection, causal ordering, spanning tree construction, minimum spanning tree construction, all–all shortest paths computation, and maximal independent set computation. In a distributed algorithm, each process has access only to its local variables and incident edge parameters. …”
Get full text

Differentiated protection strategy with dynamic traffic grooming based on clustering by Yu XIONG, Yuan-yuan LI, Jian-bo TANG, Ying ZHAO, Ru-yan WANG

“…To make dynamic traffic grooming faster and more efficient,and achieve an intelligent differentiated protection,a differentiated protection strategy with dynamic traffic grooming based on clustering(DPS-DTGC)was proposed.The whole network topology was allocated some clusters based on maximal independent set,in order to reduce the routing time consumption.Meanwhile,by the cooperation of layered auxiliary graph,residual capacity matrix and cluster aggregation layer,the traffic in inter- and intra- clusters would been groomed to realize the reasonable planning of resources and the higher efficiency of grooming.Furthermore,according to the proportion of different priority traffic in one wavelength ,the link importance was evaluated and a smart P-cycle was designed to give differentiated protection to the link.The simulation results show this strategy can make a better utilization of network resource.And with the increase of network load,it will gain a good performance in blocking rate.…”
Get full text

Research on multiflow in wireless networks based on network coding by Jin-yi ZHOU, Shu-tao XIA, Yong JIANG, Hai-tao ZHENG

“…,in the protocol interference model),the problem was formulated to compute the maximum throughput of multiple unicast flows supported by the multihop wireless network with given NC settings,in which the constraints were rebuilt from the conflict graph of hyperarcs.Furthermore,a practical algorithm was proposed to collect maximal independent sets,instead of collecting all maximal independent sets in the conflict graph of hyperarcs (which is NP-hard),and some numerical results were illustrated.…”
Get full text

Energy-Aware Distributed Intelligent Data Gathering Algorithm in Wireless Sensor Networks by Rongbo Zhu, Yingying Qin, Jiangqing Wang

“…In cluster formation phase, an energy-efficient distributed clustering scheme is proposed to form a coverage-efficient WSN, which constructs a minimum connected dominating set (MCDS) based on maximal independent sets (MISs) in distributed and localized manner, and the node with more power is selected to be the cluster head in turn to prolong the network lifetime. …”
Get full text

Counting Periodic Points in Parallel Graph Dynamical Systems by Juan A. Aledo, Ali Barzanouni, Ghazaleh Malekbala, Leila Sharifan, Jose C. Valverde

“…In order to do this, we use methods based on the notions of minimal dominating sets and maximal independent sets in graphs, respectively. More specifically, we find a lower bound for the number of fixed points and a lower bound for the number of 2-periodic points of F. …”
Get full text