A DSL for graph parallel programming with vertex subsets

The Journal of Supercomputing - The vertex-centric (VC) computation model has emerged as a promising approach for easy parallel programming and massive parallel execution for big graph processing....     

On vertex ranking of a starlike graph

A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ_r(G) is the smallest value of t such that G has a vertex t-ranking. A χ_r(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.     

A new algorithm to compute vertex cutsets in a graph

A new efficient algorithm has been presented in this paper to compute all the vertex cutsets between two specified vertices in a given symmetric graph. The algorithm has been developed into two distinct phases, i.e. in the first phase all the proper flow paths between the two specified vertices are generated, and in the second phase the vertex cutsets are determined from the information of the proper flow paths. The proposed algorithm seems to be economical in terms of computation time and it offers easy programmability on a digital computer.     

On the feedback vertex set problem for a planar graph

An algorithm solving the feedback-vertex-set problem for planar digraphs is described. In particular, planar graphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the graph. Furthermore, a side-product is a decomposition of the graph into subsets that are of interest for block-Gauß-Seidel smoothers in multi-grid methods.     

Efficiently searching a graph by a smell-oriented vertex process

Efficient graph search is a central issue in many aspects of AI. In most of existing work there is a distinction between the active “searcher”, which both executes the algorithm and holds the memory, and the passive “searched graph”, over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which most of the burden of computing and memorizing is moved from the searching agent to the nodes of the network. In this paper we suggest a method for searching an undirected, connected graph using the Vertex-Ant-Walk method, where an a(ge)nt walks along the edges of a graph G, occasionally leaving “pheromone” traces at nodes, and using those traces to guide its exploration. We show that the ant can cover the graph within time O(nd), where n is the number of vertices and d the diameter of G. The use of traces achieves a trade-off between random and self-avoiding walks, as it dictates a lower priority for already-visited neighbors. Further properties of the suggested method are: (a) modularity: a group of searching agents, each applying the same protocol, can cooperate on a mission of covering a graph with minimal explicit communication between them; (b) possible convergence to a limit cycle: a Hamiltonian path in G (if one exists) is a possible limit cycle of the process. This revised version was published online in June 2006 with corrections to the Cover Date.     

On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

An undirected biconnected graph G with nonnegative integer lengths on the edges is given. The problem we consider is that of finding a cycle basis B of G such that the length of the longest cycle included in B is the smallest among all cycle bases of G. We first observe that Horton's algorithm [SIAM J. Comput. 16 (2) (1987) 358-366] provides a fast solution of the problem that extends the one given by Chickering et al. [Inform. Process. Lett. 54 (1995) 55-58] for uniform graphs. On the other hand we show that, if the basis is required to be fundamental, then the problem is NP-hard and cannot be approximated within 2−?, ∀?>0, even with uniform lengths, unless P=NP. This problem remains NP-hard even restricted to the class of complete graphs; in this case it cannot be approximated within 13/11−?, ∀?>0, unless P=NP; it is instead approximable within 2 in general, and within 3/2 if the triangle inequality holds.     

图最短路径并行化及其应用研究

当前计算机步入移动计算时代,产生了许多新的应用,其中基于地理信息系统和位置服务的地图查询——导航就是其中之一。这类应用可以抽象为求图最短路径问题,由于节点数量巨大,传统方式不能满足用户对响应时间的要求,提出通过C/S架构来合理分配任务,并在Server端对图最短路径进行了多核、多机等不同层次的并行化,以满足用户对实时性的需求。通过对该方法和传统方法的对比评估,该方法有效缩短了用户的等待时间,提高了用户的满意度,同时减少了对移动设备电量的消耗。     

The complexity of determining a shortest cycle of even length

We study the problem of determining a shortest cycle of even length (or of odd length, respectively). For cycles of odd length we get the same complexity as for determining a shortest cycle of a graph i. e. 0 (|V|·|E|) in the case of unweighted graphs and 0 (|V|³) in the case of weighted graphs. The main contribution of this paper is an algorithm computing the shortest cycle of even length of an unweighted undirected graph within essentially 0 (|V|²) time.     

一种基于核心顶点的无参图聚类算法

针对许多经典的图聚类算法存在输入参数难以确定、时间复杂度过高、聚类精度较低等缺点,本文提出了一种无需输入参数的基于核心顶点的图聚类算法（NGCC）。该算法将相似的顶点分配到同一个簇后,再利用PageRank算法发现核心顶点以形成初始簇。然后,将剩余的未标记顶点进行分配,形成最终簇结构。实验结果证明,NGCC算法在无需任何参数的条件下,在不同规模的数据集上的聚类质量与对比的经典图聚类算法相当或更优,而且适用范围更广。     

从节点度数生成无向简单连通图

许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。     

A greedy approach to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton [A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput. 16 (1987) 358] and hereby obtain a very simple exact algorithm of complexity , being as fast as the first algorithm proposed for this problem [A polynomial time algorithm for minimum cycle basis in directed graphs, Kurt Mehlhorn's List of Publications, 185, MPI, Saarbrücken, 2004, http://www.mpi-sb.mpg.de/~mehlhorn/ftp/DirCycleBasis.ps; Proc. STACS 2005, submitted for publication]. Moreover, the speed-up of Golynski and Horton [A polynomial time algorithm to find the minimum cycle basis of a regular matroid, in: M. Penttonen, E. Meineche Schmidt (Eds.), SWAT 2002, Lecture Notes in Comput. Sci., vol. 2368, Springer, Berlin, 2002, pp. 200-209] applies to this problem, providing an exact algorithm of complexity , in particular . Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.     

Efficient processing of shortest path queries in evolving graph sequences

In many applications, information is best represented as graphs. In a dynamic world, information changes and so the graphs representing the information evolve with time. We propose that historical graph-structured data be maintained for analytical processing. We call a historical evolving graph sequence an EGS. We observe that in many applications, graphs of an EGS are large and numerous, and they often exhibit much redundancy among them. We study the problem of efficient shortest path query processing on an EGS and put forward a solution framework called FVF. Two algorithms, namely, FVF-F and FVF-H, are proposed. While the FVF-F algorithm works on a sequence of flat graph clusters, the FVF-H algorithm works on a hierarchy of such clusters. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in shortest query processing on EGSs. Comparing FVF-F and FVF-H, the latter gives a larger speedup, is more flexible in terms of memory requirements, and is far less sensitive to parameter values.     

Reduced constants for simple cycle graph separation

 If G is an n vertex maximal planar graph and δ≤1 3, then the vertex set of G can be partitioned into three sets A, B, C such that neither A nor B contains more than (1−δ)n vertices, no edge from G connects a vertex in A to a vertex in B, and C is a cycle in G containing no more than (√2δ+√2−2δ)√n+O(1) vertices. Specifically, when δ=1 3, the separator C is of size (√2/3+√4/3)√n+O(1), which is roughly 1.97√n. The constant 1.97 is an improvement over the best known so far result of Miller 2√2≈2.82. If non-negative weights adding to at most 1 are associated with the vertices of G, then the vertex set of G can be partitioned into three sets A, B, C such that neither A nor B has weight exceeding 1−δ, no edge from G connects a vertex in A to a vertex in B, and C is a simple cycle with no more than 2√n+O(1) vertices. Received: 8 September 1993/11 December 1995     

图的赋权路径矩阵与所有点对最短路径问题

给出了二维元素矩阵的概念,对于赋权图对应的赋权矩阵,定义了二维元素初始赋权路径矩阵和二维元素一般赋权路径矩阵,在通常赋权矩阵“乘法”运算基础上定义了路径“乘法”运算,从而得到了二维元素一般赋权路径矩阵的“乘法”运算,通过其“乘法”运算来求出所有点对的最短距离与对应路径,在得到最短距离的同时也得到对应的路径,结果显示在最终的一般赋权路径矩阵上。该算法易于通过计算机编程实现,对于大规模有向图或无向图,更有优势。     

基于粘贴模型的图顶点着色问题的DNA算法

为了用生化实验的方法解决图的顶点着色问题,基于粘贴模型的巨大并行性,将着色问题转化为可满足性问题,提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤,并对生化反应过程进行了模拟,得出具体的着色方案,证明了该算法的可行性。     

A distributed shortest path algorithm for a planar network

An algorithm is presented for finding a single source shortest path tree in a planar undirected distributed network with nonnegative edge costs. The number of messages used by the algorithm is O(n^5/3) on an n-node network. Distributed algorithms are also presented for finding a breath-first spanning tree in general network, for finding a shortest path tree in a general network, for finding a separator of a planar network, and for finding a division of a planar network.