(n,k)-冒泡排序网络的子网络可靠性

并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用.为了精确度量基于(n,k)-冒泡排序网络构建的并行计算机系统的子网络容错能力,建立了(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络与特定字符串之间的一一对应关系,研究了点故障模型下(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络的...     

Conditional matching preclusion for the alternating group graphs and split-stars

The matching preclusion number of a graph is the minimum number of edges the deletion of which results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges the deletion of which results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this article, we find this number and classify all optimal sets for the alternating group graphs, one of the most popular interconnection networks, and their companion graphs, the split-stars. Moreover, some general results on the conditional matching preclusion problems are also presented.     

Conditional matching preclusion for the arrangement graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper we find this number and classify all optimal sets for the arrangement graphs, one of the most popular interconnection networks.     

k元n维冒泡排序网络的子网排除

在并行计算机系统中,元器件和线路故障普遍存在,而系统的容错能力可以通过其底层基础网络的拓扑性质衡量。为了精确度量以k元n维冒泡排序网络为底层拓扑结构的并行计算机系统的容错能力,结合其层次结构和子网划分特征,分别提出了节点故障模型和线路故障模型下攻击该网络中所有k－m元n－m维冒泡排序子网络的算法,确定了需要攻击的最优节点集合和最优线路集合。根据算法可得:当2≤k≤n－2,m≤k－1时,攻击k元n维冒泡排序网络中所有的k－m元n－m维冒泡排序子网络,在节点故障模型下需要攻击至少C^m_nm!个节点,在边故障模型下需要攻击至少C^m_nm!条线路。     

A sufficient condition for pancyclic graphs

In 2005, Rahman and Kaykobad proved that if G is a connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for each pair x, y of distinct nonadjacent vertices in G, where d(x,y) is the length of a shortest path between x and y in G, then G has a Hamiltonian path [Inform. Process. Lett. 94 (2005) 37–41]. In 2006 Li proved that if G is a 2-connected graph of order n3 such that d(x)+d(y)+d(x,y)n+2 for each pair x,y of nonadjacent vertices in G, then G is pancyclic or G=K_n/2,n/2 where n4 is an even integer [Inform. Process. Lett. 98 (2006) 159–161]. In this work we prove that if G is a 2-connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for all pairs x, y of distinct nonadjacent vertices in G, then G is pancyclic or G belongs to one of four specified families of graphs.     

BSCC(4,k)的Hamilton圈分解

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。     

A General Approach to L(h, k)-Label Interconnection Networks

Given two non-negative integers h and k,an L(h,k)-labeling of a graph G=(V,E) is a function from the set V to a set of colors,such that adjacent nodes take colors at distance at least h,and nodes at distance 2 take colors at distance at least k.The aim of the L(h,k)-labeling problem is to minimize the greatest used color.Since the decisional version of this problem is NP-complete,it is important to investigate particular classes of graphs for which the problem can be efficiently solved.It is well known that the most common interconnection topologies,such as Butterfly-like,Bene(?),CCC,Trivalent Cayley networks,are all characterized by a similar structure:they have nodes organized as a matrix and connections are divided into layers.So we naturally introduce a new class of graphs,called (1×n)-multistage graphs,containing the most common interconnection topologies,on which we study the L(h,k)-labeling.A general algorithm for L(h,k)-labeling these graphs is presented,and from this method an efficient L(2,1)-labeling for Butterfly and CCC networks is derived.Finally we describe a possible generalization of our approach.     

On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

The embedding of rings and meshes into RP(k) networks

Copyright by Science in China Press 2004 Interconnection networks, as an important means in parallel processing systems, are investigated widely[1,2]. Recently a class of lower-degree networks is proposed[2—4]. In ref. [3] we have investigated a constant degree network, called RP(k) network. Com-pared with rings and 2-D mesh networks, the RP(k) network has many good properties. The RP(k) network has a much smaller diameter than that of 2-D meshes when the number of network nodes is less …     

Construction of solitary wave solutions for variants of the K(n,n) equation

In this paper, variational iteration method and Adomian decomposition are implemented to construct solitary solutions for variants of K(n, n) equation. In these schemes the solution takes the form of a convergent series with easily computable components. The chosen initial solution or trial function plays a major role in changing the physical structure of the solution. Comparison between the two methods is made and many models are approached. The obtained results reveal that the two methods are very effective and convenient for constructing solitary solutions.     

Theory of （n） truth degrees of formulas in modal logic and a consistency theorem

The theory of (n) truth degrees of formulas is proposed in modal logic for the first time. A consistency theorem is obtained which says that the (n) truth degree of a modality-free formula equals the truth degree of the formula in two-valued propositional logic. Variations of (n) truth degrees of formulas w.r.t. n in temporal logic is investigated. Moreover, the theory of (n) similarity degrees among modal formulas is proposed and the (n) modal logic metric space is derived therefrom which contains the classical logic metric space as a subspace. Finally, a kind of approximate reasoning theory is proposed in modal logic. Supported by the National Natural Science Foundation of China (Grant Nos. 10331010 and 10771129), and the Foundation of 211 Construction of Shaanxi Normal University     

一种可压缩的(r,n)门限秘密图像共享方案

提出了一种可压缩的(r,n)门限秘密图像共享方案,Shamir的门限方案是该方案的基础,它可以克服VSS方案的缺点,并能把影子图像压缩成原秘密图像大小的1/r;当所有像素灰度值小于250时,恢复图像和原秘密图像一样。随后对该方案进行改进,使其在有像素灰度值大于250的情况下,可获得无质量损失的恢复图像。     

A sufficient condition for a graph to be an (a,b, k)-critical graph

Let G be a graph, and let a, b, k be integers with 0≤a≤b, k≥0. An [a, b]-factor of graph G is defined as a spanning subgraph F of G such that a≤d _F (x)≤b for each x∈V(G). Then a graph G is called an (a, b, k)-critical graph if after deleting any k vertices of G the remaining graph of G has an [a, b]-factor. In this article, a sufficient condition is given, which is a neighborhood condition for a graph G to be an (a, b, k)-critical graph.     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

On the bounds of feedback numbers of (n,k)-star graphs

The feedback number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. We use $f(n,k)$ to denote the feedback number of the $(n,k)$-star graph $S_{n,k}$ and $p(n,k)$ the number of k-permutations of an n-element set. This paper proves that$p(n,k)?2(k?1)!\left(\begin{array}{c}\hfill n\hfill \\ \hfill k?1\hfill \end{array}\right)?f(n,k)?p(n,k)?2(k?1)!\sum _{i=1}^{\theta }\left(\begin{array}{c}\hfill n?2i+1\hfill \\ \hfill k?i\hfill \end{array}\right),$ where $\theta =\min \{k?1,n?k+1\}$.     

A method for exact reliability of consecutive2-out-of-(r, r)-from-(n, n):F systems

A new reliability model, consecutive 2‐out‐of‐(r, r)‐from‐(n, n):F model, is proposed. The consecutive 2‐out‐of‐(r, r)‐from‐(n, n):F system consists of a square grid of side n (containing n² components) such that the system fails if and only if there is at least one square of side r which includes among them at least two failed components. For i.i.d. case an algorithm is given for computing the reliability of the system. The reliability function can be expressed by the number of 0–1 matrices having no two or more 0s at any square of side r.     

LR(k)任意文法位置的断点调试方法

LR(k)文法能描述所有确定型上下文无关语言,广泛应用于各类分析器生成器中.传统的LR(k)文法断点调试方法仅支持在产生式右部末尾设置断点(后文简称尾部断点),不支持在产生式右部中间位置设置断点(后文简称中间断点),这给分析器的开发和调试带来了不便.文中提出了一种新颖的LR(k)文法断点调试方法,不但支持传统的尾部断点,还支持中间断点.该方法可显著增加可利用的断点数量,可以跟踪到更细粒度的文法成分,从而帮助用户更好地进行文法调试,降低分析器的开发难度.     

二方共享与(t,n)门限方案相结合的容侵CA方案

分析了现有容侵CA方案,提出了一种基于二方共享与（t,n）门限方案相结合的容侵CA方案,即先由CA应用服务器（CAA）、密钥服务器（SS）共享CA私钥,而后进一步将SS的共享密钥SK2利用门限密码的思想分成n份,并由n个密钥共享服务器（SSS）共享。在签名过程中既不需要由d2i（1≤i≤n）重构SK2,也不需要由d2i（1≤i≤n）与SK1重构SK。签名被分为CAA的初次签名与SS的二次签名,在形成正式签名前CAA要与SS相互认证,一旦发现对方签名异常,可即时向仲裁中心报警,从而提高了CA系统的安全性及容侵能力。