Efficient realization of frequently used bijections on cube-connected cycles

CCC has lower hardware complexity than hypercube and is suited for current VLSI technology.LC-permutations are a large set of important permutations frequently used in various parallel computations.Existing routing algorithms for CCC cannot realize LC-permutations without network conflict.We present an algorithm to realize LC-permutations on CCC.The algorithm consists of two periods of inter-cycle transmissions and one period of inner-cycle transmissions.In the inter-cycle transmissions the dimensional links of CCC are used in a “pipeline” manner and in the inner-cycle transmissions the data packets are sorted by a part of its destination address.The algorithm is fast (O(log2N)) and no conflict will occur.     

An algorithmic mitigation of large spurious interprocedural cycles in static analysis

We present a simple algorithmic extension of the approximate call‐strings approach to mitigate substantial performance degradation caused by spurious interprocedural cycles. Spurious interprocedural cycles are, in a realistic setting, the key reasons for why approximate call‐return semantics in both context‐sensitive and ‐insensitive static analysis can make the analysis much slower than expected. In the approximate call‐strings‐based context‐sensitive static analysis, because the number of distinguished contexts is finite, multiple call‐contexts are inevitably joined at the entry of a procedure and the output at the exit is propagated to multiple return‐sites. We found that these multiple returns frequently create a single large cycle (we call it ‘butterfly cycle’) covering almost all parts of the program and such a spurious cycle makes analyses very slow and inaccurate. Our simple algorithmic technique (within the fixpoint iteration algorithm) identifies and prunes these spurious interprocedural flows. The technique's effectiveness is proven by experiments with a realistic C analyzer to reduce the analysis time by 7–96%. As the technique is algorithmic, it can be easily applicable to existing analyses without changing the underlying abstract semantics, it is orthogonal to the underlying abstract semantics' context‐sensitivity, and its correctness is obvious. Copyright © 2010 John Wiley & Sons, Ltd.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

Cycles in economic systems with open labor markets

A dynamic macromodel of an economic system with a monopsonic labor market and variable labor resources is considered. The initiation conditions for classical business cycles are investigated for this model. Bifurcation analysis of the model is performed to estimate the effect of the minimum wage on the way such cycles form. The results of theoretical analysis are supplemented with numerical experiments. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 48–72, July–August 2008.     

Temporal aggregation, systematic sampling, and the Hodrick-Prescott filter

The time aggregation properties of the Hodrick-Prescott (HP) filter, which decomposes a time series into trend and cycle, are analyzed for the case of annual, quarterly, and monthly data. Aggregation of the disaggregate components cannot be obtained as the exact result from direct application of an HP filter to the aggregate series. Employing several criteria, HP decompositions for different levels of aggregation that provide similar results can be found. The aggregation is guided by the principle that the period associated with the frequency for which the filter gain is should not be altered. This criterion is intuitive and easy to apply. It is shown that it is approximated, to the first order, by an already proposed empirical rule and that alternative, more complex criteria yield similar results. Moreover, the values of the smoothing parameter of the HP filter that provide results which are approximately consistent under aggregation are considerably robust with respect to the ARIMA model of the series. Aggregation is found to perform better for the case of temporal aggregation than for systematic sampling. The desirability of exact aggregation consistency is investigated. A clarification concerning the supposed spuriousness of the cycles obtained by the HP filter is discussed.     

化工过程的模拟培训系统

化工厂操作工用的动态模拟培训系统是丙化化工企业常用的提高员工素质的手段。本文从基本概念，作用功能，模型算法及当前发展趋势等方面做了综合评述。     

基于Local-map的Mesh光网络简单p圈构造法

圈构造算法是Mesh光网络中p圈法设计的前提。根据简单p圈的特点，针对圈构造算法问题，提出将原来圈上边变为跨接边的图扩展算法。该圈扩展算法构造的圈具有保护性能优良，并且包含所有原来的圈上的点。在圈扩展算法和Local-map概念的基础上提出了基于Local-map的p圈启发式算法，该算法在Local-map中运行固扩展算法，这样既能提高p圈的保护性能，又能使p圈位于局域范围内，保证快速恢复。对比分析Local-map和DFS两种找圈算法的实验结果，该方案构造的圈恢复速度快，容量利用率高，比较适合网状光网络中的p图设计。     

Software Process and Product Improvement: A Historical Perspective

In this paper, a historical overview of significant attempts to get over the software crisis is presented. In particular, we trace the development of lifecycle models and information systems development methodologies during the last four decades. Finally, we explore the role of measurements and outline current and future works leading to process and product improvement.     

二分图中含大圈的 2―因子(英文)

本文给出了均衡二分图有一个2-因子恰含 k 个大圈的度条件。设 G = (V1,V2;E) 是一个二分图,满足 |V1| = |V2| = n ≥ sk,其中 s ≥ 3 和 k ≥ 1 是两个整数。如果图 G 的最小度至少为 (1 ? 1/s)n + 1,那么 G 有一个2-因子恰含 k 个圈使得每个圈长至少为 2s。     

由按列单降矩阵给出的瓶颈TSP的一个迭代算法

本文给出了一个求解由按列单降矩阵(Matrices graded up its columns)给出的瓶颈旅行商问题(Bottleneck TSP)的迭代算法,证明了算法是可实现的且只需要多项式界的迭代时间。算法揭示了这类问题的一个极好性质,即任意2—邻域内的最优解必为同题的全局最优解。