Greedy algorithms for generalized k-rankings of paths

A k-ranking of a graph is a labeling of the vertices with positive integers 1,2,…,k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let Pn be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of Pn. In this paper we investigate two generalizations of rankings. We first consider bounded (k,s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider kt-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number to be the smallest number of labels that can be used in a (k,s)-ranking and show for n?2, where i=⌊log₂(s)⌋+1. We define the kt-rank number, to be the smallest number of labels that can be used in a kt-ranking. We present a recursive formula that gives the kt-rank numbers for paths, showing for all an−1<j?an where {an} is defined as follows: a₁=1 and an=⌊((t+1)/t)an−1⌋+1.     

A level set method based on the Bayesian risk for medical image segmentation

This paper proposes an alternative criterion derived from the Bayesian risk classification error for image segmentation. The proposed model introduces a region-based force determined through the difference of the posterior image densities for the different classes, a term based on the prior probability derived from Kullback-Leibler information number, and a regularity term adopted to avoid the generation of excessively irregular and small segmented regions. Compared with other level set methods, the proposed approach relies on the optimum decision of pixel classification and the estimates of prior probabilities; thus the approach has more reliability in theory and practice. Experiments show that the proposed approach is able to extract the complicated shapes of targets and robust for various types of medical images. Moreover, the algorithm can be easily extendable for multiphase segmentation.     

在Red Hat Linux操作系统下设置拨号服务器

出于系统安全考虑,许多计算机应用系统采用UNIX/Linux操作系统,即应用服务采用UNIX操作系统服务器,GUI客户界面应用使用Linux工作站;同样处于安全考虑,系统远程维护多采用modem拨号方式.不同于Windows操作系统提供的图形界面操作,在UNIX/Linux操作系统环境下配i PPP拨入服务器过程需要多...     

Numerical investigations on dynamic stall of low Reynolds number flow around oscillating airfoils

This paper presents a 2D computational investigation on the dynamic stall phenomenon associated with unsteady flow around the NACA0012 airfoil at low Reynolds number (Re_c ≈ 10⁵). Two sets of oscillating patterns with different frequencies, mean oscillating angles and amplitudes are numerically simulated using Computational Fluid Dynamics (CFD), and the results obtained are validated against the corresponding published experimental data. It is concluded that the CFD prediction captures well the vortex-shedding predominated flow structure which is experimentally obtained and the results quantitatively agree well with the experimental data, except when the blade is at a very high angle of attack.     

基于完全平方数的RSA密码分析算法机理

给出基于完全平方数的RSA密码分析算法的机理,分析满足同余式x2≡y2 (mod n)的完全平方数x和y的数域选择与算法效率的关系。通过数学证明和相关分析方法,定义RSA公钥n的素因子特征c,证明当c>2时,如果数域范围选择和构造的算法得当,则分解n的效率较高,当c<2时,使算法的运算数域增大,可以降低分解n的效率和有效性,即构造的RSA密码是安全的。     

动态的网络实时连接控制机制

动态网络连接控制(DNCC)试图根据系统的动态安全状态特征对计算机接入网络的行为进行控制,从而保证接入计算机在网络连接过程中的持续安全性,防止一次性安全认证后接入计算机发生安全状态变化给系统带来的可能破坏.DNCC采取系统安全策略作为计算平台安全状态评价指标,准确地反映了计算平台状态的动态变化特征,克服了目前网络接入控制主流技术中的安全状态保证瞬时性缺点.统计和分析结果表明,DNCC具有良好的性能和实现可行性.     

城际客运专线收费系统设计

为了让旅客出行更便捷,提出了城际客运专线收费系统设计方法.建立了收费系统总体结构模型,阐述了实现其功能的过程和方法,指出了乘车IC卡在收费系统中具有关键作用.对乘车IC卡结构原理、外观结构、技术方法进行了设计.最后通过创建收费系统B/S结构功能模块,测试了用乘车卡卡号在数据库中建立乘客ID、预存费用、分配座位、记录乘车行程标识、计算乘车路程、收取乘车费用、自助订票等功能,验证收费系统设计的可行性.     

演变图上的连接子图演变模式挖掘

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表明,挖掘结果在真实应用中具有实际意义.     

Cops and Robbers from a distance

Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance k Cops and Robbers, where the cops win if at least one of them is of distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written c_k(G), equals the minimum number of cops needed to win at a given distance k. We study the parameter c_k from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded c_k(G) values and develop an O(n^2s+3) algorithm for determining if c_k(G)≤s for s fixed. We prove that if s is not fixed, then computing c_k(G) is NP-hard. Upper and lower bounds are found for c_k(G) in terms of the order of G. We prove that

     

Numerical solutions of unsteady flows with low inlet Mach numbers

This study deals with a numerical solution of a 2D unsteady flow of a compressible viscous fluid in a channel for low inlet airflow velocity. The unsteadiness of the flow is caused by a prescribed periodic motion of a part of the channel wall with large amplitudes, nearly closing the channel during oscillations. The channel is a simplified model of the glottal space in the human vocal tract and the flow can represent a model of airflow coming from the trachea, through the glottal region with periodically vibrating vocal folds, and to the human vocal tract.