On the L(2, 1)-labelling of block graphs

The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k.

In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3.     

Distance three labellings for K n ×K 2

In a wireless communication network, the channel assignment problem addresses the correct assignment of a frequency to each transmitter in the network. To avoid interference between two nearby transmitters, the assigned frequencies must satisfy certain conditions related to the distance between transmitters. We can use only a limited number of channels; hence, we have to minimize the range of frequencies used. The distance labelling of a graph is a mathematical model of the channel assignment problem derived from the work of Hale [Frequency assignment: Theory and application, Proc. IEEE 68 (1980), pp. 1497–1514]. Lam et al. [L(j, k)-labelings for the products of complete graphs, J. Comb. Optim. 14 (2007), pp. 219–227] addressed distance two labelling for the direct product K _n ×K _m of complete graphs K _n and K _m . In this paper, we solve the distance three labelling problem for K _n ×K ₂.     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

Game chromatic number of graphs with locally bounded number of cycles

We consider the coloring game and the marking game on graphs with bounded number of cycles passing through any edge. We prove that the game coloring number of a graph G is at most c+4, if every edge of G belongs to at most c different cycles. This result covers two earlier bounds on the game coloring number: for trees (c=0) and for cactuses (c=1).     

Radio Link Frequency Assignment

The problem of radio frequency assignment is to provide communication channels from limited spectral resources whilst keeping to a minimum the interference suffered by those whishing to communicate in a given radio communication network. This problem is a combinatorial (NP-hard) optimization problem. In 1993, the CELAR (the French Centre d'Electronique de l'Armement) built a suite of simplified versions of Radio Link Frequency Assignment Problems (RLFAP) starting from data on a real network Roisnel93. Initially designed for assessing the performances of several Constraint Logic Programming languages, these benchmarks have been made available to the public in the framework of the European EUCLID project CALMA (Combinatorial Algorithms for Military Applications). These problems should look very attractive to the CSP community: the problem is simple to represent, all constraints are binary and involve finite domain variables. They nevertheless have some of the flavors of real problems (including large size and several optimization criteria). This paper gives essential facts about the CELAR instances and also introduces the GRAPH instances which were generated during the CALMA project.     

NC-OFDM在认知无线电中应用的仿真研究

认知无线电环境中,可用频谱具有分布宽、非连续和动态变化的特性。为了解决环境中数据传输的问题,研究设计能够适应频谱特性的通信系统。首先对系统所处的电磁环境进行动态频谱感知,估计出当前时刻的频谱信息,然后根据频谱信息对系统子载波进行裁剪,只利用未被授权用户使用的子载波以NC-OFDM作为传输技术进行数据传送。当通信环境动态变化时,验证系统是否能够准确的估计出当前的频谱信息,然后仿真比较NC-OFDM和NC-MC-CDMA系统的误码性能,并对其结果进行讨论分析。仿真结果表明:NC-OFDM技术能够适应认知环境中可用频谱的特性,且NC-OFDM系统比NC-MC-CDMA系统具有更好的误码性能。     

On the stability number of the edge intersection of two graphs

Let G be the graph obtained as the edge intersection of two graphs G₁, G₂ on the same vertex set V. We show that if at least one of G₁, G₂ is perfect, then α(G)?α(G₁)·α(G₂), where α() is the cardinality of the largest stable set. Moreover, for general G₁ and G₂, we show that α(G)?R(α(G₁)+1,α(G₂)+1)−1, where R(k,?) is the Ramsey number.     

The oriented chromatic number of Halin graphs

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H. The oriented chromatic number of an unoriented graph G is the maximal chromatic number over all possible orientations of G. In this paper, we prove that every Halin graph has oriented chromatic number at most 8, improving a previous bound by Hosseini Dolama and Sopena, and confirming the conjecture given by Vignal.     

梯图的点可区别全染色（n=7（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法——三角排序,利用该排序的结果证明了当n=7（mod8）且Cn-1^4/2＋2〈m≤Cn ^4/2＋2时,梯图Lm≌Pm×P2的点可区别全色数为n。     

TFRC在认知无线电环境中的性能分析及改进

TCP友好速率控制协议(TCP Friendly Rate Control,TFRC)能够有效支持多媒体传输,而其在认知无线电环境中少有研究.本文通过在认知无线电环境中对TFRC进行仿真,考察了①感知周期,②主用户干扰,③信道异构性三个因素对TFRC性能的影响,进而提出了一种反馈机制改善TFRC对频谱切换前后信道容量变化适应的能力.实验结果表明TFRC性能与信道检测时长和主用户行为有着密切关系,提出的改进方法可以有效的提高TFRC在认知无线电环境中的性能.     

基于区间数型多因素指派模型的多传感器优化分配方法

如何在不确定的复杂环境下优化分配有限的传感器资源是传感器管理系统中的一个关键问题.在用区间数来描述这种不确定性研究思路的基础上, 提出了一种新的区间数型多因素指派模型的求解方法. 首先, 给出了拓展的区间数型多因素指派模型. 然后, 采用不确定有序加权平均 (Uncertain ordered weighted average, UOWA) 算子集结规范化后的区间数型效率矩阵, 通过逼近理想解的排序法 (Technique for order preference by similarity to ideal solution, TOPSIS) 确定综合效率矩阵. 进一步将其转化为标准型指派问题, 最后通过匈牙利法得到最优解. 通过算例说明了该方法解决多传感器优化分配问题的有效性.     

On the modular inversion hidden number problem

We give a rigorous deterministic polynomial time algorithm for the modular inversion hidden number problem introduced by D. Boneh, S. Halevi and N.A. Howgrave-Graham in 2001. For our algorithm, we need to be given about 2/3 of the bits of the output, which matches one of the heuristic algorithms of D. Boneh, S. Halevi and N.A. Howgrave-Graham and answers one of their open questions. However their more efficient algorithm that requires only 1/3 of the bits of the output still remains heuristic.     

A meta-heuristic algorithm to solve quadratic assignment formulations of cell formation problems without presetting number of cells

The purpose of cellular manufacturing (CM) is to find part-families and machine cells which form self-sufficient units of production with a certain amount of autonomy that result in easier control (Kusiak, 1987, 1990). One of the most important steps in CM is to optimally identify cells from a given part-machine incidence matrix. Several formulations of various complexities are proposed in the literature to deal with this problem. One of the mostly known formulations for CM is the quadratic assignment formulation (Kusiak and Chow, 1988). The problem with the quadratic assignment based formulation is the difficulty of its solution due to its combinatorial nature. The formulation is also known as NP-hard (Kusiak and Chow, 1988). In this paper a novel simulated annealing based meta-heuristic algorithm is developed to solve quadratic assignment formulations of the manufacturing cell formation problems. In the paper a novel solution representation scheme is developed. Using the proposed solution representation scheme, feasible neighborhoods can be generated easily. Moreover, the proposed algorithm has the ability to self determine the optimal number of cell during the search process. A test problem is solved to present working of the proposed algorithm.     

认知Mesh网络中的多信道MAC协议设计

现有认知无线Mesh网动态信道接入协议在利用空闲授权信道进行数据传输时,冲突概率较大。为此,提出一种基于声望模型的信道分配算法。该算法通过对各个授权信道传输的历史经验进行学习,使认知用户能够获取每个授权信道的声望值。在信道协商阶段,接收方认知用户根据信道的声望值大小,从可用信道集合中选取出期望传输成功率最高的信道,能较好地减少多个认知用户在同一空闲授权信道上的竞争,并有效降低认知用户与主用户发生冲突的概率。仿真结果表明,该算法能有效提高认知用户传输数据报文的成功率,增加网络的整体吞吐量。     

超宽带冲激无线电相关接收器的仿真比较

超宽带相关接收器的设计是超宽带冲激无线电接收机实现信号接收的关键之一,针对使用二阶高斯脉冲的超宽带冲激无线电相关接收器的特点,建立了相应的仿真模型,在Simulink平台下实现了对超宽带冲激无线电相关接收器的模拟,采用了T-R(发送-参考)自相关和互相关三种相关接收机方案,分别通过高斯噪声信道和多径信道进行相关仿真,对比了各种相关接收器的脉冲检测效果,验证了相关检测技术从噪声环境中提取超宽带信号的能力,为超宽带相关接收机系统的优化设计提供了参考.     

基于遗传算法的全双工认知无线电网络信道分配策略研究

随着无线通信业务的不断增长和智能终端的日益多样化,无线频谱资源变得愈加紧缺,认知无线电作为一项能够有效解决频谱利用率过低的技术,近年来引起了学术界和工程界的广泛关注。在认知无线电网络中,次用户以合作频谱感知的方式智能判断主用户的工作状态,以便在授权频谱的空闲时段内接入并加以使用。将全双工通信技术引入到传统的认知无线电网络中,实现了频谱感知和数据传输的同步,既能确保数据传输的连续性,又能减少对主用户的干扰,对提升无线频谱利用率具有重要作用。对于多信道全双工认知无线电网络的信道分配,建立了次级网络吞吐量最大化模型,并通过惩罚函数法,将混合整数非线性规划问题转换成不带约束条件的非线性规划问题,提出了基于遗传算法的全双工认知无线电网络信道分配策略。仿真实验结果表明,该算法能在综合考虑算法复杂度和性能的情况下,完成信道分配并保证次级网络吞吐量的最大化。     

双模终端射频电路设计

随着第三代移动通信终端的问世,TD—Scdma／GSM手机是适应于移动网络的最新产品终端。该文正是在第三代手机大规模商用之际,提出的3G终端射频设计。