期刊文献+
共找到17篇文章
< 1 >
每页显示 20 50 100
Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization 被引量:1
1
作者 Basma Mohamed Linda Mohaisen Mohamed Amin 《Intelligent Automation & Soft Computing》 SCIE 2023年第5期2349-2361,共13页
In this paper,we consider the NP-hard problem offinding the minimum connected resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distanc... In this paper,we consider the NP-hard problem offinding the minimum connected resolving set of graphs.A vertex set B of a connected graph G resolves G if every vertex of G is uniquely identified by its vector of distances to the ver-tices in B.A resolving set B of G is connected if the subgraph B induced by B is a nontrivial connected subgraph of G.The cardinality of the minimal resolving set is the metric dimension of G and the cardinality of minimum connected resolving set is the connected metric dimension of G.The problem is solved heuristically by a binary version of an enhanced Harris Hawk Optimization(BEHHO)algorithm.This is thefirst attempt to determine the connected resolving set heuristically.BEHHO combines classical HHO with opposition-based learning,chaotic local search and is equipped with an S-shaped transfer function to convert the contin-uous variable into a binary one.The hawks of BEHHO are binary encoded and are used to represent which one of the vertices of a graph belongs to the connected resolving set.The feasibility is enforced by repairing hawks such that an addi-tional node selected from V\B is added to B up to obtain the connected resolving set.The proposed BEHHO algorithm is compared to binary Harris Hawk Optimi-zation(BHHO),binary opposition-based learning Harris Hawk Optimization(BOHHO),binary chaotic local search Harris Hawk Optimization(BCHHO)algorithms.Computational results confirm the superiority of the BEHHO for determining connected metric dimension. 展开更多
关键词 connected resolving set binary optimization harris hawks algorithm
下载PDF
(α,β)-constraints connected dominating set algorithm in wireless sensor network
2
作者 孙彦景 钱建生 +1 位作者 顾相平 陈光柱 《Journal of Southeast University(English Edition)》 EI CAS 2008年第4期414-419,共6页
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. 展开更多
关键词 wireless sensor network connected dominating set transmission delay maximal independent set power consumption
下载PDF
Area-Based Connected Dominating Set Construction and Maintenance Algorithm in Ubiquitous Stub Environment 被引量:1
3
作者 Guo Shaoyong Xing Ningzhe +2 位作者 Fu Ning Shao Sujie You Fucheng 《China Communications》 SCIE CSCD 2015年第9期141-149,共9页
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. 展开更多
关键词 connected dominating set ubiquitous stub network timer MANET
下载PDF
An effective connected dominating set based mobility management algorithm in MANETs
4
作者 Xin-yu WANG Xiao-hu YANG +3 位作者 Jian-ling SUN Wei LI Wei SHI Shan-ping LI 《Journal of Zhejiang University-Science A(Applied Physics & Engineering)》 SCIE EI CAS CSCD 2008年第10期1318-1325,共8页
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. 展开更多
关键词 Mobile ad hoc network (MANET) connected dominating set (CDS) MOBILITY Dominator No-key dominator Approximation factor
下载PDF
AN EFFICIENT DISTRIBUTED ALGORITHM FOR CONNECTED DOMINATING SET CONSTRUCTION IN WIRELESS SENSOR NETWORKS
5
作者 Yang Zongkai Zhao Dasheng +1 位作者 Wang Yuming He Jianhua 《Journal of Electronics(China)》 2005年第6期671-675,共5页
Efficient broadcasting protocols based on Connected Dominating Set (CDS) are frequently used;hence the entire broadcast domain is restricted to nodes in the CDS. This letter proves that a node must be a CDS node, if i... Efficient broadcasting protocols based on Connected Dominating Set (CDS) are frequently used;hence the entire broadcast domain is restricted to nodes in the CDS. This letter proves that a node must be a CDS node, if its neighbors with larger keys cannot cover it together.Then a simple distributed CDS construction algorithm is proposed, which is more effective than the existing algorithms in reducing the dominating set size and the computation complexity at the same time. Simulation results also confirm this, especially in relatively dense networks. 展开更多
关键词 Sensor network BROADCAST connected Dominating Set (CDS)
下载PDF
Paired, Total, and Connected Domination on the Queen’s Graph Revisited
6
作者 Paul A. Burchett 《Open Journal of Discrete Mathematics》 2016年第1期1-6,共6页
The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that... The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that every square of an n × n board is attacked? Beginning in 2005 with Amirabadi, Burchett, and Hedetniemi [2] [3], work on this problem, and two other related problems, has seen progress. Bounds have been given for the values of all three domination parameters on the queen’s graph. In this paper, formations of queens are given that provide new bounds for the values of total, paired, and connected domination on the queen’s graph, denoted , , and respectively. For any n × n board size, the new bound of is arrived at, along with the separate bounds of , for with , and , for with . 展开更多
关键词 CHESS Total Dominating Set Paired Dominating Set connected Dominating Set
下载PDF
L(h, k)-Labeling of Circulant Graphs
7
作者 Sarbari Mitra Soumya Bhoumik 《Journal of Applied Mathematics and Physics》 2023年第5期1448-1458,共11页
An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adj... An L(h,k)-labeling of a graph G is an assignment of non-negative integers to the vertices such that if two vertices u and v are adjacent then they receive labels that differ by at least h, and when u and v are not adjacent but there is a two-hop path between them, then they receive labels that differ by at least k. The span λ of such a labeling is the difference between the largest and the smallest vertex labels assigned. Let λ<sub>h</sub>k</sup>  ( G )denote the least λ such that G admits an L(h,k) -labeling using labels from {0,1,...λ}. A Cayley graph of group is called circulant graph of order n, if the group is isomorphic to Z<sub>n.</sub> In this paper, initially we investigate the L(h,k) -labeling for circulant graphs with “large” connection sets, and then we extend our observation and find the span of L(h,k) -labeling for any circulants of order n. . 展开更多
关键词 Channel Assignment L(h k)-Labeling CIRCULANTS Connection Set
下载PDF
A Distributed Virtual Backbone Formation for Wireless Ad Hoc and Sensor Networks 被引量:2
8
作者 曹涌涛 何晨 蒋铃鸽 《Journal of Shanghai Jiaotong university(Science)》 EI 2007年第1期23-28,34,共7页
The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set (CDS) was proposed as a virtual backbone to improve the performance of wireless netwo... The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set (CDS) was proposed as a virtual backbone to improve the performance of wireless networks. The quality of a virtual backbone is measured not only by approximation factor, which is the ratio of its size to that of minimum CDS, but also time complexity and message complexity. In this paper, a distributed algorithm is presented to construct a minimum CDS for ad hoc and sensor networks. By destroying triangular loops in the virtual backbone, the proposed algorithm can effectively construct a CDS with smaller size. Moreover, our algorithm, which is fully localized, has a constant approximation ratio, linear message and time complexity, and low implementation complexity. The simulation results and theoretical analysis show that our algorithm has better efficiency and performance than conventional approaches. 展开更多
关键词 virtual backbone connected dominating sets(CDS) wireless sensor networks
下载PDF
Backbone formulation algorithm in wireless sensor network based on cross-entropy method 被引量:8
9
作者 SHI Weiren JIANG Yisong ZHAO Ying 《Instrumentation》 2014年第1期38-48,共11页
In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected domi... In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected dominating set in an arbitrary graph.In this paper,based on cross-entropy method,we present a novel backbone formulation algorithm(BFA-CE)in wireless sensor network.In BFA-CE,a maximal independent set is got at first and nodes in the independent set are required to get their action sets.Based on those action sets,a backbone is generated with the cross-entropy method.Simulation results show that our algorithm can effectively reduce the size of backbone network within a reasonable message overhead,and it has lower average node degree.This approach can be potentially used in designing efficient broadcasting strategy or working as a backup routing of wireless sensor network. 展开更多
关键词 wireless sensor network BACKBONE connected dominated set cross-entropy method
下载PDF
A Research for Regional Contribution Rate of Internal Source and External Source of PM_(2.5) Based on Set Pair Analysis Method 被引量:1
10
作者 Zhou Yejing Zhou Jingxuan Xiao Renbin 《Meteorological and Environmental Research》 CAS 2016年第2期36-40,44,共6页
A problem of the air pollution control in China is getting to know a regional contribution rate of internal and external source of PM2.5. In this paper,Set Pair Analysis( SPA) method is proposed to calculate the con... A problem of the air pollution control in China is getting to know a regional contribution rate of internal and external source of PM2.5. In this paper,Set Pair Analysis( SPA) method is proposed to calculate the contribution rate of PM2.5in Dongguan City. Due to geographic,meteorological factors and the low concentration of air pollutants in Qingxi area,the PM2.5in this place is mainly contributed by the regional transport of air pollutants from other inside areas of Dongguan,and less affected by the outside of Dongguan. So the concentration of PM2.5in Qingxi area can reflect the Dongguan's basic background concentration of PM2.5. On the basis of the basic background concentration,firstly the concentration of each pollutant components is divided into the internal part and the mixed part. Secondly using the source apportionment samples of five monitoring sites in Dongguan we can respectively construct a sample set A and an evaluation set B. Thirdly the SPA is operated onto the mixed part in terms of set B.At last the connection degree between the concentration of each pollutant components and external source and internal source will be calculated,that is the contribution rate. The research reveals that the contribution rate of internal source and external source of PM2.5in Dongguan City is 83%and 17% respectively,which roughly met expectations. This method is simple and effective and it can provide a reference for the government taking reduction measures to control PM2.5pollutants emission. 展开更多
关键词 Set Pair Analysis Connection degree PM2.5 Internal source External source Contribution rate
下载PDF
SOME MULTIPLICITY RESULTS FOR AN ELASTIC BEAM EQUATION AT RESONANCE
11
作者 马如云 《Applied Mathematics and Mechanics(English Edition)》 SCIE EI 1993年第2期193-200,共8页
This paper deals with multiplicity results for nonlinear elastic equations of the typewheregi[0,1] X R R satisfies Caratheodory condition L2[0,1]. The solvability of this problem has been studied by several authors, b... This paper deals with multiplicity results for nonlinear elastic equations of the typewheregi[0,1] X R R satisfies Caratheodory condition L2[0,1]. The solvability of this problem has been studied by several authors, but there isn't any multiplicity result until now to the author's knowledge. By combining the Lyapunov-Schmidt procedure with the technique of connected set, we establish several multiplicity results under suitable condition. 展开更多
关键词 multiplicity results elastic beam equations RESONANCE technique of connected set
下载PDF
Topologically Finite Intersection Property and Minimax Theorems
12
作者 张石生 张宪 《Applied Mathematics and Mechanics(English Edition)》 SCIE EI 1995年第4期325-333,共9页
A more general lopologically finite intersection property is obtained. As anapplication,we utilize this result to obtain some more general minimax theorems. Theresults presented in this paper unify and extend the main... A more general lopologically finite intersection property is obtained. As anapplication,we utilize this result to obtain some more general minimax theorems. Theresults presented in this paper unify and extend the main results of [5, 6, 9]. 展开更多
关键词 finite intersection property minimax theorem connected set
下载PDF
A Distributed Design for Minimum 2-Connected m-Dominating Set in Bidirectional Wireless Ad-Hoc Networks 被引量:3
13
作者 Xiaofeng Gao Bosheng Xu Jun Li 《Tsinghua Science and Technology》 SCIE EI CAS 2012年第5期553-566,共14页
Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected ... Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected m-Dominating Set ((k,m)-CDS) in a network as a fault-tolerant virtual backbone to help the routing process, which will save the energy of non-dominators and improve the network performance significantly. Considering the economic cost and efficiency, we choose (2,m)-CDS as the object of this paper, which is helpful enough in practical applications and has a smaller size. We firstly study the existing algorithms for (k,m)- CDS and figure out the problems of these designs. Then we propose a new distributed algorithm named Dominating Set Based AIgorithm (DSBA) with three sub-routines: Dominating Set AIgorithm (DSA), Connection Algorithm (CA), and Connectivity Expansion Algorithm (CEA). Instead of commonly used Maximal Independent Set (MIS), we pick dominating set directly from the given graph, and then connect them by a two-step ring based connecting strategy to satisfy the 2-connectivity. We also provide the correctness and complexity analysis of DSBA. At last, we compare DSBA with the last construction Distributed Deterministic Algorithm (DDA) by several numerical experiments. The simulation results show that DSBA improves over 30 percent of the performance of DDA, proving that DSBA is more practical for real-world applications. 展开更多
关键词 connected dominating set FAULT-TOLERANCE distributed algorithm APPROXIMATION
原文传递
Approximation Algorithms for Steiner Connected Dominating Set
14
作者 Ya-Feng Wu Yin-Long Xu Guo-Liang Chen 《Journal of Computer Science & Technology》 SCIE EI CSCD 2005年第5期713-716,共4页
Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and know... Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP- hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of (2 + 1/(m - 1))H(min(△, k)) +O(1), which outperforms the previous best result (c + 1)H(min(△, k)) + O(1) in the case of m ≥ 1 +1/(c - 1), where c is the best approximation ratio for Steiner tree, A is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0 ≤ m ≤ min(△, k) and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2 ln(min(△, k)) + O(1), which can also be improved to 2 lnk if the optimal solution is greater than c·e^2c+1/2(c+1). 展开更多
关键词 approximation algorithm Steiner connected dominated set graph algorithm NP-HARD
原文传递
Constructing entire functions with non-locally connected Julia set by quasiconformal surgery
15
作者 Yanhua Zhang Gaofei Zhang 《Science China Mathematics》 SCIE CSCD 2018年第9期1637-1646,共10页
We give an alternative way to construct an entire function with quasiconformal surgery so that all its Fatou components are quasi-disks but the Julia set is non-locally connected.
关键词 entire functions quasiconformal surgery non-locally connected Julia sets
原文传递
AHBP: An Efficient Broadcast Protocol forMobile Ad Hoc Networks 被引量:6
16
作者 彭伟 卢锡城 《Journal of Computer Science & Technology》 SCIE EI CSCD 2001年第2期114-125,共12页
Broadcast is an important operation in many network protocols. It is utilized to discover routes to unknown nodes in mobile ad hoc networks (MANETs) and is the key factor in scaling on-demand routing protocols to larg... Broadcast is an important operation in many network protocols. It is utilized to discover routes to unknown nodes in mobile ad hoc networks (MANETs) and is the key factor in scaling on-demand routing protocols to large networks. This paper presents the Ad Hoc Broadcast Protocol (AHBP) and its performance is discussed. In the protocol, messages are only rebroadcast by broadcast relay gateways that constitute a connected dominating set of the network. AHBP can efficiently reduce the redundant messages which make flooding-like protocols perform badly in large dense networks. Simulations are conducted to determine the performance characteristics of the protocol. The simulation results have shown excellent reduction of broadcast redundancy with AHBP. It also contributes to a reduced level of broadcast collision and congestion. 展开更多
关键词 PROTOCOL WIRELESS BROADCAST mobile ad hoc network connected dominating set
原文传递
Upper Bound Involving Parameter σ_2 for the Rainbow Connection Number
17
作者 Jiu-ying DONG Xue-liang LI 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2013年第4期685-688,共4页
Let G be a connected graph of order n. The rainbow connection number rc(G) of G was introduced by Chartrand et al. Chandran et al. used the minimum degree of G and obtained an upper bound that rc(G) 〈_ 3n/( δ... Let G be a connected graph of order n. The rainbow connection number rc(G) of G was introduced by Chartrand et al. Chandran et al. used the minimum degree of G and obtained an upper bound that rc(G) 〈_ 3n/( δ+ 1) - 3, which is tight up to additive factors. In this paper, we use the minimum degree-sum a2 6n of G to obtain a better bound rc(G) _〈 - 8, especially when is small (constant) but a2 is large (linear in n). 展开更多
关键词 rainbow coloring rainbow connection connected two-step dominating set parameter σ2 (G)
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部