Concurrent depth-first search algorithms based on Tarjan’s Algorithm

We present concurrent algorithms, based on depth-first search, for three problems relevant to model checking: given a state graph, to find its strongly connected components, which states are in loops, and which states are in “lassos”. Each algorithm is a variant of Tarjan’s Algorithm. Our algorithms typically exhibit a three- or four-fold speed-up over the corresponding sequential algorithms on an eight-core machine.     

A distributed graph algorithm for the detection of local cycles andknots

In this paper, a distributed cycle/knot detection algorithm for general graphs is presented. The algorithm distinguishes between cycles and knots and is the first algorithm to our knowledge which does so. It is especially relevant to an application such as parallel simulation in which 1) cycles and knots can arise frequently 2) the size of the graph is very large, and 3) it is necessary to know if a given node is in a cycle or a knot. It requires less communication than previous algorithms-2m vs. (at least) (4m) for the Chandy and Misra algorithm, where m is the number of links in the graph. It requires O (nlog (n)) bits of memory, where n is the number of nodes. The algorithm differs from the classical diffusing computation methods through its use of incomplete search messages to speed up the computation. We introduce a marking scheme in order to identify strongly connected subcomponents of the graph which cannot reach the initiator of the algorithm. This allows us to distinguish between the case in which the initiator is in a cycle (only) or is in a knot     

An Optimal Parallel Co-Connectivity Algorithm

In this paper we consider the problem of computing the connected components of the complement of a given graph. We describe a simple sequential algorithm for this problem, which works on the input graph and not on its complement, and which for a graph on n vertices and m edges runs in optimal O(n+m) time. Moreover, unlike previous linear co-connectivity algorithms, this algorithm admits efficient parallelization, leading to an optimal O(log n)-time and O((n+m)log n)-processor algorithm on the EREW PRAM model of computation. It is worth noting that, for the related problem of computing the connected components of a graph, no optimal deterministic parallel algorithm is currently available. The co-connectivity algorithms find applications in a number of problems. In fact, we also include a parallel recognition algorithm for weakly triangulated graphs, which takes advantage of the parallel co-connectivity algorithm and achieves an O(log² n) time complexity using O((n+m²) log n) processors on the EREW PRAM model of computation.     

New fast parallel algorithm for the connected component problem and its VLSI implementation

We present an O(log n) compare-exchange time parallel algorithm to compute the connected components of a given graph. We also introduce a simple regular VLSI architecture on which the proposed algorithm can readily be implemented requiring n³ identical processing elements and O(n) communication time, where n is the number of vertices in the graph.     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and “unicycular graphs.” Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.     

On computing the transitive closure of a relation

Summary An algorithm is presented for computing the transitive closure of an arbitrary relation which is based upon Tarjan's algorithm [7] for finding the strongly connected components of a directed graph. A new formulation, justifying a somewhat simplified statement of the latter, characterises weaker restrictions on the form of the graph traversal than Tarjan's depth first conditions and reveals aspects of the behaviour of this algorithm which have been obscure hitherto. If V is the number of vertices in the directed graph representing the relation then the worst case behaviour, O(V ³) is inferior to existing algorithms [1, 2] which require O(V ³/log V) and operations respectively. The best case performance, O(V ²) operations, is better. Viewed in this way, it is similar to other algorithms [5, 6, 8] but it combines the improved efficiency in the presence of strongly connected components which characterises the algorithms in [5, 6] with the advantages of Warshall's algorithm [8], namely, succinctness, a single traversal of the directed graph and ability to exploit the availability of Boolean vector operations. This research was begun while the authors were visiting Stanford University and was supported in part by National Science Foundation grant DCR72-03752 A02 and by the Office of Naval Research contract NR 044-402     

Quantum search in structured database using local adiabatic evolution and spectral methods

Since Grover’s seminal work which provides a way to speed up combinatorial search, quantum search has been studied in great detail. We propose a new method for designing quantum search algorithms for finding a marked element in the state space of a graph. The algorithm is based on a local adiabatic evolution of the Hamiltonian associated with the graph. The main new idea is to apply some techniques such as Krylov subspace projection methods, Lanczos algorithm and spectral distribution methods. Indeed, using these techniques together with the second-order perturbation theory, we give a systematic method for calculating the approximate search time at which the marked state can be reached. That is, for any undirected regular connected graph which is considered as the state space of the database, the introduced algorithm provides a systematic and programmable way for evaluation of the search time, in terms of the corresponding graph polynomials.     

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

An efficient implementation of the equilibrium algorithm for housing markets with duplicate houses

We propose an asymptotically optimal implementation of the equilibrium algorithm for housing markets with duplicate houses and strict preferences. It is based on Tarjan?s depth-first search algorithm for strongly connected components of a digraph.     

Improving exact algorithms for MAX-2-SAT

We study three new techniques that will speed up the branch-and-bound algorithm for the MAX-2-SAT problem: The first technique is a group of new lower bound functions for the algorithm and we show that these functions are admissible and consistently better than other known lower bound functions. The other two techniques are based on the strongly connected components of the implication graph of a 2CNF formula: One uses the graph to simplify the formula and the other uses the graph to design a new variable ordering. The experiments show that the simplification can reduce the size of the input substantially no matter what is the clause-to-variable ratio and that the new variable ordering performs much better when the clause-to-variable ratio is less than 2. A direct outcome of this research is a high-performance implementation of an exact algorithm for MAX-2-SAT which outperforms any implementation we know about in the same category. We also show that our implementation is a feasible and effective tool to solve large instances of the Max-Cut problem in graph theory.Preliminary results of this paper appeared in [20,21]. This research was supported in part by NSF under grant CCR-0098093.     

基于深度优先的分步分治算法研究

Top-k服务组合问题对于学术界和工业界来讲,都有实际的研究意义和应用场景。文中分析了理解top-k问题的关键所在解图,提出了基于深度优先的分步分治算法进行服务组合。该算法对用户请求的输出参数分别进行求解,该过程可并行处理,在求解结束后再进行合并。该方法可以支持分布式、并行处理框架,从而在应对大规模的服务集合时,能快速、高效地提供满足用户需求的组合服务;提出了通过构造解图的方法进行搜索求解,通过求解＂关键路径＂和＂非关键路径＂与合并＂关键路径＂和＂非关键路径＂得到解图。     

Optimisation of invariant criteria for event graphs

The problem of obtaining a cycle time that is smaller than a given value in a strongly connected event graph, while minimizing an invariant linear criterion, is addressed. This linear criterion is based on a p-invariant of the strongly connected event graph under consideration. Some properties of the optimal solution are proved, and a heuristic algorithm and an exact algorithm which make it possible to reach a solution to the problem are given. Applications of the results to the evaluation of job shops and Kanban systems are proposed     

分布式并行计算环境下混合遗传算法的研究

为提高混合遗传算法的计算效率和求解质量,提出一个并行混合遗传算法框架。该框架主要由遗传算法、小生境操作和单纯形3部分组成,遗传算法和小生境操作采用串行执行方式,单纯形采用分布式并行执行方式。分布式并行计算环境由4台计算机通过交换机连接构成,并设计了一个动态任务调度方案。一个典型工程算例验证了新算法的有效性,并且在分布式并行环境下取得了较好的加速比和并行效率。     

Stochastic relaxation on partitions with connected components andits application to image segmentation

We present a new method of segmentation in which images are segmented in partitions with connected components. We give computationally inexpensive algorithms for probability simulation and simulated annealing on the space of partitions with connected components of a general graph. In particular, Hastings algorithms (1970) and generalized Metropolis algorithms are defined to avoid heavy computation. To achieve segmentation, we propose a hierarchical approach which at each step minimizes a cost function on the space of partitions with connected components of a graph. The algorithm is applied to segment gray-level, color, and textured images     

Consensus seeking in multiagent cooperative control systems with bounded control input

Consensus algorithms in multiagent cooperative control systems with bounded control input are studied in this paper.Consensus algorithms are considered for the single-integrator dynamics and double-integrator dynamics under different communication interaction topologies,and show that consensus is reached asymptotically using the algorithm proposed in this paper for the single-integrator dynamics if the undirected interaction graph is connected,and consensus is reached asymptotically if the directed interaction graph is strongly connected,respectively.In addition,the paper further shows that consensus is reached asymptotically using the algorithm proposed for the double-integrator dynamics if the directed interaction graph is strongly connected.The effectiveness of these algorithms is demonstrated through simulations.     

Robust and parallel Uyghur text localization in complex background images

Uyghur text localization in complex background images is a significant research for Uyghur image content analysis. In this paper, we propose a robust Uyghur text localization method in complex background images and provide a CPU–GPU heterogeneous parallelization scheme. Firstly, a multi-color-channel enhanced maximally stable extremal region is used to extract components in images, which is robust to blur and low contrast. Secondly, a two-stage component classification system is used to filter out non-text components. Finally, a component connected graph algorithm is proposed to construct text lines. Experiments on the proposed dataset demonstrate that our algorithm compares favorably with the state-of-the-art algorithms when handling Uyghur texts. Besides, the heterogeneous parallel implementation achieves 12.5 times speedup.     

An improved transitive closure algorithm

Several efficient transitive closure algorithms operate on the strongly connected components of a digraph, some of them using Tarjan's algorithm [17]. Exploiting facts from graph theory and the special properties of Tarjan's algorithm we develop a new, improved algorithm. The transitive reduction of a digraph defined in [1] may be obtained as a byproduct.     

A distributed finite-time optimization algorithm for directed networks of continuous-time agents

This article proposes a new distributed finite-time optimization algorithm for agents under directed graphs. By employing the nonsmooth technique and graph theory, a distributed discontinuous algorithm for continuous-time agents subject to strongly convex local cost functions is first designed with a finite-time distributed estimator, where the gradients of the local cost functions are estimated in finite time. It is shown that for a strongly connected graph and arbitrary initial conditions, the proposed algorithms can achieve consensus, and the systems can converge to the optimal point in finite time. Then, a two-step approach is proposed to achieve finite-time optimization of high-order agents with disturbances under directed graphs. Finally, the validity of the proposed finite-time optimization algorithm is verified by two numerical examples.     

Algorithms for generalized vertex-rankings of partial k-trees

A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. A c-vertex-ranking is optimal if the number of labels used is as small as possible. We present sequential and parallel algorithms to find an optimal c-vertex-ranking of a partial k-tree, that is, a graph of treewidth bounded by a fixed integer k. The sequential algorithm takes polynomial-time for any positive integer c. The parallel algorithm takes O(log n) parallel time using a polynomial number of processors on the common CRCW PRAM, where n is the number of vertices in G.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.