网络流量的有效测量方法分析

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).     

基于压缩的大规模图的割点求解算法

割点求解是图应用中的一个重要操作.深度优先搜索树算法可以解决割点求解问题.但是该算法存在缺点,导致它不能在实际问题中得到很好的应用.这是因为当今数据的两大特点,一是数据规模庞大,对于很多图操作提出了挑战性的要求;二是数据多变,每天数据的大量更新使得传统算法必须依据更新重复计算,浪费了时间和空间.深度优先搜索树算法的时间复杂度为O(|V|+|E|),其中,|V|和|E|分别为图的顶点的数目和边的数目.它能够很好地适应第1个特点,但是对于第2个特点该算法则无能为力.提出一种基于压缩的割点求解算法来解决这个问题.该算法通过点的朴素相似来压缩图,时间复杂度为O(|E|).在得到的无损压缩图上进行割点求解,同时在压缩图上动态地维护点和边的更新,在不解压图的情况下完成图的更新,在更新后的图上进行割点求解,极大地降低了时间和空间消耗.该压缩算法得到的压缩图对其他图操作同样适用.     

公交网络下的一种费用限制最小时态路径查询索引

私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询：给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL（approximate cost constrained time labelling）.ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询,可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解,避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O（|V|·△_max·|E|·（log|E|+△_max））,其中,|V|表示顶点数,|E|表示边数,△_max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级,并分析了影响建立索引时间和空间大小的因素.     

无存储器冲突的并行快速排序算法*

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．     

分布式存储的并行串匹配算法的设计与分析

并行串匹配算法的研究大都集中在PRAM(parallel random access machine)模型上,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多.该文采用将最优串行算法并行化的技术,利用模式串的周期性质,巧妙地将改进的KMP(Knuth-Morris-Pratt)算法并行化,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法,其计算复杂度为O(n/p+m),通信复杂度为O(ulogp相似文献   

一种具有能力约束性能的任意源覆盖多播方法

近年来提出的许多面向单个数据源设计的多播树并不能简单扩展到任意源多播系统中,因为针对每个源建立一个树代价高昂.而已存在的一些允许多数据源的P2P(peer-to-peer)系统的维护量大,在体现结点能力差异等方面缺少灵活性.提出一个任意源覆盖多播服务方案,并具有结点能力约束性能.它建立在非DHT(distributed hash table)覆盖网络上,无须建立显式的多播树.设计了两种分布式多播算法,它们将任意源的多播信息传送到所有结点的期望跳数是O(log_cn),其中,c是平均结点能力,n是多播组中的结点个数.     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

一种时间复杂度最优的精确串匹配算法

现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m-1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(1og_σm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.     

并集问题的一个随机算法

随机算法由于其简洁和高效的特点正在计算中占据越来越重要的位置.但有时随机算法的优良性能并不要求用完全独立的随机变量作为它的输入.仅用成对独立的随机变量作为输入,得到了一个关于估计并集的基的问题的随机算法.这一方法可以减少随机算法中使用的随机位.对于固定的精确度ε和确信度δ,此算法需要O(t^1/2)的随机位,比标准的随机算法所使用的随机位数O(tlogtM)要少得多.而算法的执行时间并没有显著地增加O(t²logM).     

A simple and fast parallel coloring for distance-hereditary graphs

In the literature, there are quite a few sequential and parallel algorithms to solve problems on distance-hereditary graphs. Two well-known classes of graphs, which contain trees and cographs, belong to distance-hereditary graphs. We consider the vertex-coloring problem on distance-hereditary graphs. Let T/sub d/(|V|, |E|) and P/sub d/d(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree representation of a distance-hereditary graph G=(V,E) on a PRAM model M/sub d/. Our algorithm runs in O(T/sub d/(|V|, |E|)+log|V|) time using O(P/sub d/(|V|, |E|)+|V|/log|V|) processors on M/sub d/. The best known result for constructing a decomposition tree needs O(log/sup 2/ |V|) time using O(|V|+|E|) processors on a CREW PRAM. If a decomposition tree is provided as input, we solve the problem in O(log |V|) time using O(|V|/log |V|) processors on an EREW PRAM. To the best of our knowledge, there is no parallel algorithm for this problem on distance-hereditary graphs.     

A new distributed breadth-first-search algorithm

A new distributed breadth-first-search algorithm for graphs is presented. Its worst-case communication and time complexities are both O(|V|²), where |V| is the number of vertices. The existing algorithm, due to Cheung (1983), has communication and time complexities O(|V|³) and O(|V|), respectively.     

一种新的信息熵属性约简算法

给出一个区分对象对的属性约简定义,同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集,首先给出了一个快速求简化决策表的算法,其时间复杂度为O（|C||U|）。然后在简化决策表的基础上,设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为O（|C||U|）+O（|C||U/C|²）和O（|U/C|²）+O（|U|）,最后用一个实例说明了新算法的高效性。     

An efficient Dijkstra-like labeling method for computing shortest odd/even paths

We show how the problem of determining shortest paths of even or odd length between two specified vertices in a graph G = (V, E) can be reduced to the problem of finding a shortest alternating path with respect to a specific matching in a related graph H. This problem can be solved by a Dijkstra-like labeling procedure of complexity O(|V|²) respectively O(|E|log|V|). Interpreting this procedure appropriately the method can then be applied directly on the given graph G.     

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.     

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two 1

In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic. Received July 15, 1997; revised January 29, 1999, and June 23, 1999.     

渐变填充的性质和算法

本文着重研究了Jordan数字流形上的渐变填充,设计了紧缩渐变填充算法和分裂渐变填充算法;并证明:如果D是离散网格空间上的Jordan凸集,那么存在O(|D||D|)时间的紧缩算法去做渐变填充.最后,我们对Jordan正方形区域、三角域和圆盘,分别给出了它们各自的O(|D|log_2|D|)时间的分裂渐变填充算法.     

一种快速计算HU差别矩阵的属性约简算法

在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为O(|C|2|U|2).为降低该属性约简算法的时间复杂度, 首先引入简化决策表的定义,并设计了一个求简化决策表的算法,其时间复杂度为O(|C||U|).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(U/C|).最后以属性重要性为启发信息,设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(|C||U|,O(|C|2|U/C|)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.     

基于冲突域的高效属性约简算法

引入冲突域的概念,研究冲突域的性质.以冲突域中冲突对象数目的变化为度量标准,给出核属性和属性重要性的计算方法,并设计了快速求解核属性和属性重要性的算法.在此基础上,给出高效属性约简算法,该算法以核属性为初始约简集,以属性重要性为启发式信息.在最坏情况下,算法的时间复杂度为O(|C|2|U|),空间复杂度为O(|U|);实验结果表明,该算法是正确的、高效的.     

基于数据库的属性约简模型的快速求核算法

对于基于数据库系统的属性约简模型,给出相应的简化差别矩阵和相应核的定义,并证明该核与基于数据库系统的属性约简模型的核是等价的。在此基础上设计了一个新的求核算法,其时间复杂度和空间复杂度分别为max{O（|C||U/C|²）,O（|C||U|）}和O（|U|）。