一种借助邻接矩阵求任意图最大团的方法

最大团问题是图论中重要的NPC问题。文章以一种新的方法,通过矩阵运算选择图上可能存在最大团的分支,进而实现求解最大团的问题。算法的每一个步骤都可以用成熟的并行方法替代。     

基于GPU的并行最小生成树算法的设计与实现*

针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的minreduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语缩短关键步骤的查找时间,从而获得较高效率。实验表明,相对于传统CPU实现算法和不使用原语的算法,该算法具有较明显的性能优势。     

二部图所有极大匹配的求解算法

二部图是一种十分重要的数据结构。在对二部图及匹配的概念进行了阐述后。给出了求二部图所有极大匹配的算法。该算法也可用于求二部图的所有最大匹配和完全匹配。用C语言程序验证了此算法的有效性。     

无向图在计算机绘图中的应用

本文把笔式绘图仪绘图过程时间最少的调度问题转换为在加权无向图中求解最优H-回路,并且利用最小生成树、欧拉回路、非二部图赋权匹配的算法给出了一种近似调度算法,旨在减少绘图仪移动空走时间和换笔时间,从而提高绘图效率。本算法经RP-MF160等绘图仪应用,效率提高约15%。     

求解图的最大独立集的一种算法

如何寻找图的最大独立集这个问题是一个古老的难题。文章从图论的基本概念入手 ,得到了一种基于图的邻接矩阵的寻找图的极大独立集和最大独立集的算法 ,并得到其算法复杂度为 O(nn!/(m!(n - m) !) )     

面向子流的低延迟数据调度算法

P2P流媒体是分发流媒体数据的高效方式,而数据传输延迟是决定P2P流媒体系统性能的重要参数。在分析"拉"模式数据调度模式传输延迟的基础上,本文在"推"、"拉"混合的调度模式下提出一种新的面向子流的低延迟数据调度算法。首先子流的调度问题被转换成等价的带权二部图匹配问题,其次针对转换后的二部图改进匈牙利算法,提出最小延迟、最大匹配的启发式匹配算法。该算法在保证最大匹配的同时使得每条子流的延迟尽可能地低。模拟实验表明本文的算法能够极大降低数据传输延迟。     

无向完全图的哈密顿回路

一、引言判断一个图是否有Hamilton回路的充要条件一直没有解决,尽管充分条件与必要条件都有了,而且人们对图的研究已经非常深入——一个例子是竞赛图的研究。在这里我们通过对求无向完全图的哈密顿回路总数的探讨,引申Hamilton回路的求法,另一个引申就是NP完全问题的解法。当然,这里引申出来的方法仍然是完全搜索式的,但在下面对完全图的Hamilton回路的分析中可以看到,里面没有重复的情况。比     

采用高斯混合模型及树结构的立体匹配算法

针对传统立体匹配算法无法同时为图像边缘和低纹理区域提供一个合适大小的聚合窗口而导致匹配精度较低的难题,提出一种结合高斯混合模型及最小生成树结构的立体匹配算法。通过图像初始视差、像素颜色及距离信息将图像分为初始若干区域及待分割候选像素;基于高斯混合模型并行迭代更新各区域参数,得到最终的分割;在各分割上建立最小生成树计算聚合值求取视差;通过邻域内的有效视差修正误匹配点,获取精度较高的稠密视差图。与其他算法相比,该算法能有效降低误匹配率,尤其在深度不连续区域的匹配效果显著改善。     

简单图中若干子图枚举问题的统一算法

本文对简单图的独立集、团、对集、路、无弦路、弦回路、有向完全子图及传递有向路的枚举问题给出了统一算法及有关算法正确性和计算复杂性的理论结果。     

基于图匹配的多处理机调度算法

本文对具有高通讯延迟的多处理机系统（机群系统）上的任务调度算法进行了研究，与以往算法主要考虑任务图的关键路径不同，本文给出了任务图的调度与其偶图匹配的对应关系，并由此提出了一种新的启发式算法，通过模拟试验显示本算法具有较好的调度效果。     

Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs

The problem of computing minimum distortion embeddings of a given graph into a line (path) was introduced in 2004 and has quickly attracted significant attention with subsequent results appearing at recent stoc and soda conferences. So far, all such results concern approximation algorithms or exponential-time exact algorithms. We give the first polynomial-time algorithms for computing minimum distortion embeddings of graphs into a path when the input graphs belong to specific graph classes. In particular, we solve this problem in polynomial time for bipartite permutation graphs and threshold graphs. For both graph classes, the distortion can be arbitrarily large. The graphs that we consider are unweighted.     

Enumerating all connected maximal common subgraphs in two graphs

We represent a new method for finding all connected maximal common subgraphs in two graphs which is based on the transformation of the problem into the clique problem. We have developed new algorithms for enumerating all cliques that represent connected maximal common subgraphs. These algorithms are based on variants of the Bron–Kerbosch algorithm. In this paper we explain the transformation of the maximal common subgraph problem into the clique problem. We give a short summary of the variants of the Bron–Kerbosch algorithm in order to explain the modification of that algorithm such that the detected cliques represent connected maximal common subgraphs. After introducing and proving several variants of the modified algorithm we discuss the runtimes for all variants by means of random graphs. The results show the drastical reduction of the runtimes for the new algorithms.     

A Functional Approach to External Graph Algorithms

We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/ O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.     

Clique-perfectness and balancedness of some graph classes

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P₄-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P₄-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.     

A Functional Approach to External Graph Algorithms

Abstract. We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/ O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.     

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing an MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.     

A matrix-algebraic formulation of distributed-memory maximal cardinality matching algorithms in bipartite graphs

We describe parallel algorithms for computing maximal cardinality matching in a bipartite graph on distributed-memory systems. Unlike traditional algorithms that match one vertex at a time, our algorithms process many unmatched vertices simultaneously using a matrix-algebraic formulation of maximal matching. This generic matrix-algebraic framework is used to develop three efficient maximal matching algorithms with minimal changes. The newly developed algorithms have two benefits over existing graph-based algorithms. First, unlike existing parallel algorithms, cardinality of matching obtained by the new algorithms stays constant with increasing processor counts, which is important for predictable and reproducible performance. Second, relying on bulk-synchronous matrix operations, these algorithms expose a higher degree of parallelism on distributed-memory platforms than existing graph-based algorithms.We report high-performance implementations of three maximal matching algorithms using hybrid OpenMP-MPI and evaluate the performance of these algorithm using more than 35 real and randomly generated graphs. On real instances, our algorithms achieve up to 200 × speedup on 2048 cores of a Cray XC30 supercomputer. Even higher speedups are obtained on larger synthetically generated graphs where our algorithms show good scaling on up to 16,384 cores.     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

图的最大公共连通子图问题研究

图像识别、恶意代码族群特征提取、人工智能中许多应用问题都可以规约为一类图的最大公共连通子图问题。提出了求解简单最大连通子图问题的矩阵方法,定义了图特征相关度和图度序列相关系数的概念,最后结合算例给出了一种求解一般最大公共连通子图问题的贪婪算法,能够快速有效地找到一个尽可能大的公共连通子图。     

任意图支配集精确算法回顾

该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集、最大独立集、最小独立支配集、最小连通支配集、最小加权支配集问题提供了详尽算法描述和实例说明,以使文章自包含方便阅读.文中还讨论了诸如分支简化策略、复杂度分析、测度分析、记忆等技术.自Claude Berge首次准确阐述现代图支配概念后,经过很长一段时期的沉寂,关于指数时间精确算法设计的研究热情在过去五年中显著增涨.除回顾这些最新成果之外,作者还盼望国内研究团体能更加重视这个快速发展的研究领域.