关于冒泡排序连通圈网络猜想的一个注记

冒泡排序连通圈网络BSCC(n)是一类重要的互连网络,它是3正则的.2010年师海忠提出了如下猜想:冒泡排序连通圈BSCC(n)(n≥4)可分解为边不交的一个Hamilton圈和一个完美对集的并.在本文中证明了当nn==5,4时猜想成立,另外,给出了BSCC(6)的一个圈分解.     

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r -正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。     

关于互连网络群论模型的一簇猜想

连通图生成的Cayley图是作为互连网络的群论模型提出来的概念。猜想:设G=(V,E)是具有顶点集{1,2,…,n}(n>2)和m条边的连通图。如果m=2r,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并;如果m=2r+1,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m－2k个完美对集的并。特别地,对于k=r和星网络,这个猜想的特殊情形是1998年由师海忠提出来的。     

关于修正冒泡排序网络的一簇猜想

修正冒泡排序网络是互连网络设计中的一个重要的Cayley图模型,关于修正冒泡排序网络的一簇猜想如下:对于任意的自然数n≥3,修正冒泡排序网络Yn是i个边不交的哈密尔顿圈以及n-2i个完美对集的并,其中1≤i≤︱n/2︱。证明了当i=1,2时,这个猜想是正确的。     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈.文中提出了变换的方法来寻找图中的Hamilton圈,即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈.由此,设计了一个在Edmonds意义下的有效算法--自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换,证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n2).最后通过应用实例说明该算法的有效性和实用性.     

基于超立方体和圈的细胞分裂生长网络及其性质

立方连通圈是超立方体的有界变型,在这篇文章中作者以立方连通圈网络CCC(n)(n>2)为基础设计了一种新网络--CCC(n,k)(n>2且k是非负数),它是3正则3连通的,且有许多好的性质。作者证明了CCC(3,0)是哈密尔顿连通图,且CCC(n,k)(n>2且k是非负数)是哈密尔顿图,但当k>2和n>2或者k=1和22且k是非负数)和C_m的笛卡尔积的一些性质。     

关于煎饼网络及层次环煎饼网络的几个猜想

煎饼网络是由互连网络的群论模型设计出来的一类典型的超级计算机互连网络。关于煎饼网络师海忠提出了一个猜想-猜想1,但煎饼网络有一个弱点即结点度随着规模的增大而迅速增大,为了改进这一缺点师海忠提出了互连网络的层次环群论模型。在这篇文章中,首先,汪生龙给出了煎饼网络当n=5时的两种圈分解,其次师海忠提出了关于该网络的一个猜想-猜想2,当Cayley图层次环网络中的Cayley图取煎饼网络时得到煎饼层次环网络的猜想-猜想2/,进而汪生龙证明了猜想2/在低维度情形下是正确的     

带有条件故障边的k元2方体的圈嵌入

[k]元[n]方体已经成为分布式储存并行系统最常用的网络拓扑结构。研究带有条件故障边的[k]元2方体的圈嵌入问题,证明了在[k≥4]为偶整数的[k]元2方体中,若其故障边数不超过3且每个顶点至少与两条非故障边相关联,那么该[k]元2方体存在长度在4到[k2]间的任意偶长的无故障圈。     

LHL-立方体互连网络及其性质

并行计算系统一直是计算机科学中的重要研究领域,其互连网络的拓扑性质对整个网络的性能起着非常重要的作用.目前已经提出多种互连网络,其中超立方体具有对数级的直径、高连通度、对称性等很好的性质,故被用作多种并行机的处理器连接的拓扑结构.然而,超立方体并非所有性质都是最优的互连网络,且超立方体的许多变型结构具有许多比超立方体更好的性质,其中已经证明了局部扭立方体在直径、Hamilton连通性等方面都优于超立方体.给出在超立方体与局部扭立方体的顶点间的一种连接方式--超连接,从而得到一种称为LHL-立方体的新型网络,并对这种网络的以下性质进行了研究:顶点连通度、边连通度、Hamilton连通性、直径.研究结果表明,一个n维LHL-立方体是一个具有2n个顶点和n2n-1条边的n-正则图,n维LHL-立方体的顶点连通度和边连通度均为n,且是Hamilton连通的,直径上界为[n/2 ]+3.     

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

并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了精确度量基于(n,k)-冒泡排序网络构建的并行计算机系统的子网络容错能力,建立了(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络与特定字符串之间的一一对应关系,研究了点故障模型下(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络的可靠性。当2≤k≤n-2,1≤m≤k-1时,首先在概率故障条件下给出了(n,k)-冒泡排序网络中存在无故障的(n-m,k-m)-冒泡排序子网络的概率估计,并通过仿真实验验证了所得结果的精确性;其次,得出了不同数目的(n-m,k-m)-冒泡排序子网络保持无故障状态的平均失效时间的计算公式,仿真实验表明理论结果与仿真结果趋于一致。     

面向时序图数据的快速环枚举算法

时序图数据是一类边上带有时间戳信息的图数据.在时序图数据中,时序环是边满足时间戳递增约束的回路.时序环枚举在现实中有着很多应用,它可以帮助挖掘金融网络中的欺诈行为.此外,研究时序环的数量对于刻画不同时序图的特性也有重要作用.基于2018年由Rohit Kumar等人提出的时序环枚举算法（2SCENT算法）,提出一种通过添加环路信息来削减搜索空间的新型时序环枚举算法.所提出的算法为一个两阶段的算法：1）首先,通过遍历原图获得所有可能会形成环路的节点,以及相应的时间和长度信息;2）然后,利用以上信息进行动态深度优先搜索,挖掘所有的满足约束条件的环.在4个不同的真实时序图数据集上进行了大规模的实验,并以2SCENT算法作为基准对算法进行了对比.实验结果表明,所提出的算法较之前最好的2SCENT算法要快50%以上.     

一种基于Contourlet变换的图像去噪方法

在变换域阚值去噪过程中，阈值的选取和阚值处理方法至关重要。提出一种基于conmurlet变换的图像去噪方法。采用分层阈值，为每一级contourlet系数选取一个阈值。阈值处理中给出一种基于邻域的阈值处理方法，不仅考虑单个系数幅值的大小，而且考虑它的邻域系数幅值的大小。同时为了抑制在去噪图像边缘附近的伪吉布斯效应，引入cycle spinning来抑制这种图像失真。实验结果表明，利用文中去噪方法进行去噪比其他方法得到更好的视觉效果和更高的PSNR值。     

一种LDPC码校验矩阵消短环算法

LDPC码是一种逼近香农限、易实现和系统复杂度低的优秀的线性纠错码。本文中提到的LDPC码中的0-1矩阵问题就是:对给定的校验矩阵H(0-1矩阵),找到一个同阶的最好的循环置换扩张矩阵E以及适当最小正整数q,使得校验矩阵H中的所有短环(长度为4或不超过6)被消去,也即对应的E中整数的正负和不为q的倍数。最后实现了该算法。     

Minimum Cycle Bases for Network Graphs

The minimum cycle basis problem in a graph G = (V,E) is the task to construct a minimum length basis of its cycle vector space. A well-known algorithm by Horton of 1987 needs running time O(|V||E|^2.376). We present a new combinatorial approach which generates minimum cycle bases in time O(\max{|E|³,|E||V|²log |V|}) with a space requirement of (|E|²). This method is especially suitable for large sparse graphs of electric engineering applications since there, typically, |E| is close to linear in |V|.     

SWAT-DayCent coupler: An integration tool for simultaneous hydro-biogeochemical modeling using SWAT and DayCent

Process-based numerical models in environmental science can help understand and quantify terrestrial material cycles in nature. However, the existing models usually focus on the cycles of one or more elements (e.g., water, carbon, or nitrogen). For example, hydrological models such as Soil and Water Assessment Tool (SWAT) focus on the water cycle and nutrient loadings at watershed scale, whereas biogeochemical models such as DayCent (i.e., daily CENTURY) emphasize carbon/nitrogen storage and fluxes of ecosystems at landscape scale. Therefore, using either one of the two categories of models is not enough for understanding/solving the current complex environmental issues that involve multiple aspects. Although use of both models (SWAT and DayCent) could be an expedient way toward treating the problem, creating separate model projects for a single area could be challenging and time consuming, and integration/analyses of model results have some limitations due to the non-uniformity of input spatial data between models. To overcome this issue, we developed an integrated model implementation coupler that aims to drive SWAT and DayCent—the two representative models in hydrology and biogeochemistry, respectively—just using a user's SWAT project without the need of any extra efforts such as developing a framework or preparing input data for DayCent modeling. This software is easy to use and would be promising for conducting comprehensive environmental impact assessment involving hydrological and biogeochemical cycles at watershed scale.     

软件生命周期模型与CMM实施*

对于采用不同软件生命周期模型的项目在实施CMM 当中遇到的实际问题及其产生机理进行了深入分析,并提出初步的解决方案,主要涉及:采用迭代式生命周期模型的项目在实施需求管理过程域的部分内容时难以满足CMM 的要求,建议通过扩展基线的概念,采用分步基线化、分块基线化的方法予以处理;软件产品工程过程域的内容更多地针对瀑布模型,针对迭代式生命周期的内容较少,因而在实际使用迭代式生命周期模型时,工程活动不能局限于CMM 的内容.建议对CMM 中的工作产品与迭代式生命周期模型中的工作产品进行映射,并采用迭代式生命周期模型中的方法和概念作为替代实践以符合软件产品工程过程域的要求.     

北斗系统信号捕获方法研究综述

目前针对北斗信号捕获技术研究较多,但缺少系统的分类、总结和性能比较的问题。按照单周期、多周期、辅助捕获三个标准进行研究;同时,分析了捕获算法的硬件实现现状,对国内外捕获研究领域的相关方法进行了系统的整理和综述;对捕获方法进行了性能对比,仿真验证了各自的优劣,指出了北斗系统捕获技术所面临的问题和未来的发展趋势,对捕获领域加强了理论支撑。     

Minimum Weakly Fundamental Cycle Bases Are Hard To Find

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C _i in such that is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log ₂ n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log ₂ n⌉∑ _e∈E(G) w _e , thus allowing a fast 2⌈log ₂ n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.     

Cycle time distribution of cyclic networks with blocking

An algorithm is provided to compute the cycle time distribution for cyclic closed exponential queueing networks with N finite capacity nodes and blocking. The blocking phenomenon is due to the nodes with finite capacity queues which can be used to represent systems with limited resources. Moreover, a recursive algorithm is provided to evaluate the cycle time moments, and a closed form solution, both in terms of distribution and moments of the cycle time, is provided for the model under special constraints.     

时变信道复指数基频率盲估计

在基于基展开模型的时变信道盲辨识中,可通过估计复指数基频率将时变信道的盲辨识问题转换为线性时不变信道的盲辨识问题。为了更准确地实现复指数基频率的盲估计,针对两种不同输入条件下的观测数据,分别提出了利用特定二阶循环矩和四阶循环累积量方法来进行估计。特定二阶循环矩方法比传统方法更容易提取基频率分量;四阶循环累积量方法比四阶循环矩方法具有更好的抗噪声性能。理论和仿真分析证明了这两种算法的有效性。