基于子图的随机图点覆盖2度点核化研究

点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形予图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论:2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ(χ)的随机图的参数化点覆盖问题(G,k),当k小于某一与φ(х)有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.     

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

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

一种基于链暗示技术的Min-CVCB问题的精确算法

随着VLSI(超大规模集成电路)技术的发展,关于可重构阵列二分图的受约束最小点覆盖(Min-CVCB)问题受到了很多文献的关注.作为点覆盖问题的子问题,该问题已被证明是NP-完全问题.人们利用核心化和分支即使给出了时间复杂度为O((ku k1)|G| 1.26ku k1)的目前最好算法,然而仍不能满足实际工程的需要.通过进一步深入分析二分图的结构,对含有权值大于或等于3的块的连通子图分析其可能连接情况后充分利用"链暗示"技术和分枝搜索技术来建立起新的搜索递推关系;对于分枝后的块提出了一种动态规划算法,其可在多项式时间内完成处理.整个参数算法的运行时间为O((ku k1)|G| 1.1892ku k1),极大地改进了目前的最好结果.     

一种新的拓扑参数及其蛋白质网络 关键节点识别 *

针对已有拓扑参数对关键蛋白识别度不高的现状,根据蛋白质网络的特点,结合参数计算方法,提出一 个新的用来描述节点重要性的拓扑参数—— —点覆盖参数。为了避开该参数精确求解方法中可能出现的NP- 难 问题,从稀疏网络出发,在研究低度点核化技术的基础上,将确定算法与非确定算法相结合,提出基于随机核化 的快速算法（A_R_K算法）。实验结果显示,所获得的点覆盖参数不仅可以有效地描述网络节点的拓扑重要性, 而且其关键蛋白识别度也明显高于其他参数。     

一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法

二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为：当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖（ku,kl）时,对任意给定的近似率δ=1＋ε〉1,一定可以找到一个受约束近似点覆盖（ku,kl）,对应的近似率为max{ku^＊/ku,kl^＊/kl}≤1＋ε,整个近似算法的运行时间复杂度为O（22/ε）。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案（polynomial time approximation scheme,PTAS算法）。     

具有统计不相关性的核化图嵌入算法

提出统计不相关的核化图嵌入算法,为求解各种统计不相关的核化降维算法提供了一种统一方法。与已有核化降维算法相比,新的特征提取方法降低甚至消除了最佳鉴别矢量间的统计相关性,提高了识别率。通过在ORL,YALE和FERET人脸库上的实验结果表明,提出的具有统计不相关的核化图嵌入算法在识别率方面好于已有的核算法。另外,揭示了统计不相关的核化图嵌入与已有的核化图嵌入的内在关系。     

无线传感器网络中基于Voronoi图的覆盖和连通综合配置协议

着重研究无线传感器网络随机部署下的覆盖和连通问题的解决方案,尤其是当无线传感器节点的通信半径Rc与感应半径Rs之比小于2时的解决方案.本文提出了无线传感器网络中一个基于Voronoi图的覆盖和连通的综合配置协议(VIP).该协议采用了一种分布式节点冗余判断算法以判断无线传感器网络中节点的冗余性,并让节点据此来对自身进行相应的职能调度.该协议能够在Rc/Rs为任意值时保证网络的覆盖和连通性能.本文还将该协议进行了推广,使得该协议能够满足覆盖度和连通度动态变化的要求,保证网络的k-度覆盖和k-度连通.     

基于最小点覆盖及多参数方法的关键蛋白识别

针对已有方法对关键蛋白识别度不高的现状,认为进一步提高识别度有两条途径：一是发现与关键蛋白关系更密切的参数,二是充分挖掘现有参数的信息并进行有效地整合。由于点覆盖在网络（图）拓扑结构上的重要地位而研究将其引入关键蛋白质的识别中：针对算法的复杂性引进参数计算的相关算法将复杂度大幅度降低的同时对蛋白质网络进行最小点覆盖分析并获得一种新的拓扑参数-点覆盖参数,相关分析表明该参数与关键蛋白有着密切的联系。进一步研究发现,参数之间相关性的大小在很大程度上预示它们所蕴含的关键蛋白信息之间互补性的强弱,根据这一发现探讨利用包括点覆盖在内的各个参数的有限信息进行有效整合,仿真结果证实该方法能明显提高关键蛋白识别度。     

基于并行图计算框架大规模图最大流加速算法

最大流是一个重要的图计算问题,很多实际场景中如城市车流量和排水管道的排水量等问题若转化为最大流问题可以得到有效的解决.已有工作从多个角度对最大流问题进行了探讨,但仍存在一些问题.针对一些分布式图计算系统进行图分割计算复杂度较高,多次计算存在大量冗余工作等问题,提出基于GraphChi框架的大规模图最大流加速算法.根据原图中的割点构建覆盖图,给定源点和汇点后确定覆盖图中唯一路径,在GraphChi框架上并行求解覆盖图路径上各子图的最大流,找到各子图最大流的最小值即为原图的最大流值.在美国路网数据集的测试结果表明,提出的算法可显著缩短大规模图的最大流计算时间并且空间复杂度较低,有很好的加速效果.     

最多叶子生成树问题的核化算法

对算法领域的最多叶子生成树问题进行了深入研究,提出了对简单连通图2度节点的化简规则,并证明了不含2度节点的图的生成树的叶子节点数的下限为(N+6)/4,给出了构造这样一棵生成树的构造性方法.基于上述化简规则和所证明的结论,给出了最多叶子生成树问题的核化算法,该核化算法可以在O(n2)时间内得到一个4k-6大小的线性核.对于这样一个较小的核,将大大提高相关的参数算法和近似算法的性能.     

Crown Structures for Vertex Cover Kernelization

Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are studied and compared both theoretically and experimentally with each other and with older, more primitive kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crown-free subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.     

On Making a Distinguished Vertex of Minimum Degree by Vertex Deletion

For directed and undirected graphs, we study how to make a distinguished vertex the unique minimum-(in)degree vertex through deletion of a minimum number of vertices. The corresponding NP-hard optimization problems are motivated by applications concerning control in elections and social network analysis. Continuing previous work for the directed case, we show that the problem is W[2]-hard when parameterized by the graph’s feedback arc set number, whereas it becomes fixed-parameter tractable when combining the parameters “feedback vertex set number” and “number of vertices to delete”. For the so far unstudied undirected case, we show that the problem is NP-hard and W[1]-hard when parameterized by the “number of vertices to delete”. On the positive side, we show fixed-parameter tractability for several parameterizations measuring tree-likeness. In particular, we provide a dynamic programming algorithm for graphs of bounded treewidth and a vertex-linear problem kernel with respect to the parameter “feedback edge set number”. On the contrary, we show a non-existence result concerning polynomial-size problem kernels for the combined parameter “vertex cover number and number of vertices to delete”, implying corresponding non-existence results when replacing vertex cover number by treewidth or feedback vertex set number.     

基于层序遍历的顶点不变量及其图不变量

为了寻找更好性能的图不变量，利用层序遍历过程中的顶点数据经加权累加定义 了15 种顶点不变量，每一种顶点不变量排序后可以组成一种图不变量。层序遍历时将顶点度数 分为同层度数、向前度数和向后度数，其中同层度数和向后度数包含回路数信息。依据对顶点 的细分能力，挑选出3 种顶点不变量，组成图不变量，其不同组合对于各种非同构连通图具有 较好的区分性能，不仅对图顶点数N≤8 的非同构图全部可以区分，而且将N=9 的不可区分图 数量从文献[9]的989 种降到40 种，且其简并度将趋近2，随机测试表明这些图不变量具有很好 的区分度。     

On Cutwidth Parameterized by Vertex Cover

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 ^k n ^O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 ^n/2 n ^O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP?coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.     

A Cubic Kernel for Feedback Vertex Set and Loop Cutset

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k ³) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k ³) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.     

Finding Minimum Vertex Covering in Stochastic Graphs: A Learning Automata Approach

Structural and behavioral parameters of many real networks such as social networks are unpredictable, uncertain, and have time-varying parameters, and for these reasons, deterministic graphs for modeling such networks are too restrictive to solve most of the real-network problems. It seems that stochastic graphs, in which weights associated to the vertices are random variables, might be better graph models for real-world networks. Once we use a stochastic graph as the model for a network, every feature of the graph such as path, spanning tree, clique, dominating set, and cover set should be treated as a stochastic feature. For example, choosing a stochastic graph as a graph model of an online social network and defining community structure in terms of clique, the concept of a stochastic clique may be used to study community structures’ properties or define spreading of influence according to the coverage of influential users; the concept of stochastic vertex covering may be used to study spread of influence. In this article, minimum vertex covering in stochastic graphs is first defined, and then four learning, automata-based algorithms are proposed for solving a minimum vertex-covering problem in stochastic graphs where the probability distribution functions of the weights associated with the vertices of the graph are unknown. It is shown that through a proper choice of the parameters of the proposed algorithms, one can make the probability of finding minimum vertex cover in a stochastic graph as close to unity as possible. Experimental results on synthetic stochastic graphs reveal that at a certain confidence level the proposed algorithms significantly outperform the standard sampling method in terms of the number of samples needed to be taken from the vertices of the stochastic graph.     

Bimagic Vertex Labelings

The notion of the equivalence of vertex labelings on a given graph is introduced. The equivalence of three bimagic labelings for regular graphs is proved. A particular solution is obtained for the problem of the existence of a 1-vertex bimagic vertex labeling of multipartite graphs, namely, for graphs isomorphic with K_{n, n, m}. It is proved that the sequence of bi-regular graphs K_n(ij)?=?((K_n???1???M)?+?K₁)???(u_nu_i)???(u_nu_j) admits 1-vertex bimagic vertex labeling, where u_i, u_j is any pair of non-adjacent vertices in the graph K_n???1???M, u_n is a vertex of K₁, M is perfect matching of the complete graph K_n???1. It is established that if an r-regular graph G of order n is distance magic, then graph G + G has a 1-vertex bimagic vertex labeling with magic constants (n?+?1)(n?+?r)/2?+?n² and (n?+?1)(n?+?r)/2?+?nr. Two new types of graphs that do not admit 1-vertex bimagic vertex labelings are defined.