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.展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
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 .展开更多
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. .展开更多
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.展开更多
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.展开更多
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.展开更多
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.展开更多
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].展开更多
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.展开更多
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).展开更多
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.
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.展开更多
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).展开更多
文摘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.
基金Major Program of the National Natural Science Foundation of China (No.70533050)High Technology Research Program ofJiangsu Province(No.BG2007012)+1 种基金China Postdoctoral Science Foundation(No.20070411065)Science Foundation of China University of Mining andTechnology(No.OC080303)
文摘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.
基金supported by the National Science and Technology Support Program of China (2015BAG10B01)the Science and Technology Project of State Grid Corporation of China (SGIT0000KJJS1500008)
文摘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.
文摘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.
基金Supported by the National Natural Science Foundation of China (No.60202005).
文摘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.
文摘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 .
文摘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. .
基金The National Natural Science Foundation ofChina(No.60272082)The Important Science and Technology Key Item of Shanghai(No.05dzl5004)
文摘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.
基金supported partially by the science and technology project of CQ CSTC(No.cstc2012jjA40037)
文摘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.
基金Supported by National Natural Science Foundation of China(71171089)Research for PM_(2.5) Contamination Characteristics and Prevention and Control Countermeasures in Dongguan City(Dongcaidan[2013]222)
文摘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.
文摘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.
文摘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].
基金Supported by the National Natural Science Foundation of China (Nos. 61033002 and 61202024)
文摘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.
基金国家自然科学基金,'Research on Routing and Wave length assignment in WDM All-optical Networks'
文摘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).
基金supported by National Natural Science Foundation of China (Grant Nos. 11171144 and 11325104)
文摘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.
基金the National '863' High-Tech Programme of China (No. 863- 300- 01-03-99 ).
文摘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.
基金Supported by the National Natural Science Foundation of China(No.11071130)the Fundamental Research Funds for the Central Universities
文摘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).