Multicut问题参数算法的改进

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*的最好算法.     

任意多边形顶点凸、凹性判别的简捷算法

给出了一种确定任意多边形顶点凸、凹性的简捷算法.该算法只需要2n+4次乘法,5n+10次加、减法及2n+3次比较即可完成(n是多边形顶点的个数).同时,给出了任意简单多边形走向的充要条件.     

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

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

低度图的最大团求解算法

在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。     

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

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

多跳中继无线网络资源复用的建模及算法设计

建立了中继网络资源复用问题的图论模型,依据该模型设计了自适应资源复用调度算法ARRS(adaptive resource reuse scheduling),以提高中继网络资源利用率.由于ARRS算法的核心步骤涉及顶加权图G(V,E,W)的染色,是NP-hard问题,为此给出了求解最优资源复用约束的顶加权图染色的近似算法ARRS_Greedy.该算法被证明具有时间复杂度O(|V|²),近似比为?(Δ+1)/2?(Δ表示图G顶点度数的最大值).该近似比是紧的.仿真分析验证了近似算法ARRS_Greedy在应用中取得了与最优解非常接近的性能,证明了ARRS算法能够动态适应网络状态变化,因而与现有算法相比大幅度提高了系统容量.     

近似最近邻归约问题在泊松点过程上的再研究

在已发表文献中, 研究了基于图灵归约求解$ \varepsilon $-NN的问题, 即给定查询点q、点集P及近似参数$ \varepsilon $, 找到q在P中近似比不超过$ 1 + \varepsilon $的近似最近邻, 并提出了一个具有${\rm{O}}(\log n)$查询时间复杂度的图灵归约算法, 这里的查询时间是调用神谕的次数. 经过对比, 此时间优于所有现存的归约算法. 但是已发表文献中提出的归约算法的缺点在于, 其预处理时间和空间复杂度中有${\rm{O}}({(d/\varepsilon )^d})$的因子, 当维度数d较大或者近似参数$ \varepsilon $较小时, 此因子将变得不可接受. 因此, 重新研究了该归约算法, 在输入点集服从泊松点过程的情况下, 分析算法的期望时间和空间复杂度, 将算法的期望预处理时间复杂度降到${\rm{O}}(n\log n)$, 期望空间复杂度降到${\rm{O}}(n\log n)$, 而期望查询时间复杂度保持${\rm{O}}(\log n)$不变, 从而完成了在已发表文献中所提出的未来工作.     

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

无重叠条件严格模式匹配的高效求解算法

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法，与同类挖掘方法相比，该方法更容易发现有价值的频繁模式，其核心问题是计算给定模式在序列中的支持度或出现数，进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现，然后剪枝无用结点的方式计算模式的支持度，其计算时间复杂度为O （m×m×n×W），其中，m，n和W分别为模式长度、序列长度及最大间隙.为了进一步提高无重叠条件模式匹配计算速度，从而有效地降低无重叠条件序列模式挖掘时间，提出了一种高效的算法，该算法将模式匹配问题转换为一棵网树，然后从网树的最小树根结点出发，采用回溯策略迭代搜索最左孩子方式计算无重叠最小出现，在网树上剪枝该出现后，无需进一步查找并剪枝无效结点即可实现问题的求解.理论证明了该算法的完备性，并将该算法的时间复杂度降低为O （m×n×W）.在此基础上，继续指明该问题还存在另外3种相似的求解策略，分别是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最右双亲方式.实验结果验证了该算法的性能，特别是在序列模式挖掘中，应用该方法的挖掘算法可以降低挖掘时间.     

多连通多边形的内部Voronoi图的顶点和边数的上界

多边形的Voronoi图在路径规划、碰撞检测等方面有着广泛的应用,其顶点和边数在这些应用算法的复杂度分析方面起着重要作用.Held证明了一个简单多边形的内部Voronoi图最多有n+k-2个顶点和2(n+k)-3条边,其中n和k分别是多边形的顶点和内尖点数.但其结论不能适用于多连通多边形.对多连通多边形进行研究,通过将其Voronoi图转化为有根树,并利用有根树的性质,给出了其内部Voronoi图的顶点和边数上界的估计,并对Voronoi区域的边界所包含顶点和边数的平均值进行了讨论."SDU数字博物馆"系统所采用的基于Voronoi图的可见性算法的复杂度分析,就利用了所得出的结论.     

Two fixed-parameter algorithms for Vertex Covering by Paths on Trees

Vertex Covering by Paths on Trees with applications in machine translation is the task to cover all vertices of a tree T=(V,E) by choosing a minimum-weight subset of given paths in the tree. The problem is NP-hard and has recently been solved by an exact algorithm running in O(C⁴⋅²|V|) time, where C denotes the maximum number of paths covering a tree vertex. We improve this running time to O(C²⋅C⋅|V|). On the route to this, we introduce the problem Tree-like Weighted Hitting Set which might be of independent interest. In addition, for the unweighted case of Vertex Covering by Paths on Trees, we present an exact algorithm using a search tree of size O(k²⋅k!), where k denotes the number of chosen covering paths. Finally, we briefly discuss the existence of a size-O(k²) problem kernel.     

Finding the closed partition of a planar graph

In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n^1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.This work was supported in part by NSF Grant CCR 89-10707.     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。     

An O(2<Superscript>O(k)</Superscript>n<Superscript>3</Superscript>) FPT Algorithm for the Undirected Feedback Vertex Set Problem

We describe an algorithm for the Feedback Vertex Set problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(c^kn³) where c = 10.567 and n is the number of vertices in the graph. The best previous algorithms were based on the method of bounded search trees, branching on short cycles. The best previous running time of an FPT algorithm for this problem, due to Raman, Saurabh and Subramanian, has a parameter function of the form 2^{O(k log k /log log k)}. Whether an exponentially linear in k FPT algorithm for this problem is possible has been previously noted as a significant challenge. Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general form of the problem, where a subset of the vertices may be marked as forbidden to belong to the feedback set. We also establish "exponential optimality" for our algorithm by proving that no FPT algorithm with a parameter function of the form O(2^o(k)) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT = M[1].     

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.     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.     

Approximation of satisfactory bisection problems

The Satisfactory Bisection problem means to decide whether a given graph has a partition of its vertex set into two parts of the same cardinality such that each vertex has at least as many neighbors in its part as in the other part. A related variant of this problem, called Co-Satisfactory Bisection, requires that each vertex has at most as many neighbors in its part as in the other part. A vertex satisfying the degree constraint above in a partition is called ‘satisfied’ or ‘co-satisfied,’ respectively. After stating the NP-completeness of both problems, we study approximation results in two directions. We prove that maximizing the number of (co-)satisfied vertices in a bisection has no polynomial-time approximation scheme (unless P=NP), whereas constant approximation algorithms can be obtained in polynomial time. Moreover, minimizing the difference of the cardinalities of vertex classes in a bipartition that (co-)satisfies all vertices has no polynomial-time approximation scheme either.     

A factoring approach for the Steiner tree problem in undirected networks

In communication networks, many applications, such as video on demand and video conferencing, must establish a communications tree that spans a subset K in a vertex set. The source node can then send identical data to all nodes in set K along this tree. This kind of communication is known as multicast communication. A network optimization problem, called the Steiner tree problem (STP), is presented to find a least cost multicasting tree. In this paper, an O(|E|) algorithm is presented to find a minimum Steiner tree for series-parallel graphs where |E| is the number of edges. Based on this algorithm, we proposed an O(2^2c·|E|) algorithm to solve the Steiner tree problem for general graphs where c is the number of applied factoring procedures. The c value is strongly related to the topology of a given graph. This is quite different from other algorithms with exponential time complexities in |K|.