Search

A tree (tour) cover of an edge-weighted graph is a set of edges which forms a tree (closed walk) and covers every other edge in the graph. Arkin et al. [1] give approximation algorithms with ratios 3.55 (tree cover) and 5.5 (tour cover). We present algorithms with a worst-case ratio of 3 for both problems.

In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements.

Nowadays, Hadoop is massively used to store large data generated by various sources. These data are often represented in large scale graphs to solve real world problems. To compute those data, many Bulk Synchronous Parallel(BSP) model based graph processing systems are available on top of hadoop such as Pregel and Stanford: Graph Processing System (GPS). The problem of graph coloring is to assign color to all the vertices such that no neighbor vertices have same color. The graph coloring problem has many practical application in real world data analytics. In this paper, we have compared the heuristic graph coloring algorithm with BSP model based on hadoop such as Local Maxima First, Local Minima-Maxima First, Local Largest Degree First, Local Smallest-Largest Degree First. We experimented our algorithms on real world graph dataset on our hadoop cluster. The result shows that Local Smallest-Largest Degree First algorithm perform better than other heuristic based algorithms, in term of runtime and number of color used.

High performance parallel kernels for solving graph problems are complex and difficult to write. Some systems have been developed to facilitate the implementation of these kernels but the code they produce does not always perform as well as custom software. In this space, we propose Tiled Linear Algebra (TLA), a multi-level system based on linear algebra but with explicit parallel extensions. Programs can be first written in a conventional manner using linear algebra and then tuned for parallel performance using our extension. This separation allows programmers with different expertise to focus on their strengths with writing original codes that can then be tuned by parallel experts.

Graph similarity join has become imperative for integrating noisy and inconsistent data from multiple data sources. The edit distance is commonly used to measure the similarity between graphs. To accelerate the similarity join based on graph edit distance, in the paper, we make use of a preprocessing strategy to remove the mismatching graph pairs with significant differences. Then a novel method of building indexes for each graph is proposed by grouping the nodes which can be reached in k hops for each key node with structure conservation, which is the k-hop-tree based indexing method. Experiments on real and synthetic graph databases also confirm that our method can achieve good join quality in graph similarity join. Besides, the join process can be finished in polynomial time.

Minimum spanning tree (MST) based clustering algorithms have been employed successfully to detect clusters of heterogeneous nature. Given a dataset of n random points, most of the MST-based clustering algorithms first generate a complete graph G of the dataset and then construct MST from G. The first step of the algorithm is the major bottleneck which takes O(n 2) time. This paper proposes two algorithms namely MST-based clustering on K-means Graph and MST-based clustering on Bi-means Graph for reducing the computational overhead. The proposed algorithms make use of a centroid based nearest neighbor rule to generate a partition-based Local Neighborhood Graph (LNG). We prove that both the size and the computational time to construct the graph (LNG) is O(n 3/2), which is a \(O(\sqrt n)\) factor improvement over the traditional algorithms. The approximate MST is constructed from LNG in \(O(n^{3/2} \lg n)\) time, which is asymptotically faster than O(n 2). The advantage of the proposed algorithms is that they do not require any parameter setting which is a major issue in many of the nearest neighbor finding algorithms. Experimental results demonstrate that the computational time has been reduced significantly by maintaining the quality of the clusters obtained from the MST.

The problem of finding connected components in a graph is common to several applications dealing with graph analytics, such as social network analysis, web graph mining and image processing. The exponentially growing size of graphs requires the definition of appropriated computational models and algorithms for their processing on high throughput distributed architectures. In this paper we present cracker, an efficient iterative algorithm to detect connected components in large graphs. The strategy of cracker is to iteratively grow a spanning tree for each connected component of the graph. Nodes added to such trees are discarded from the computation in the subsequent iterations. We provide an extensive experimental evaluation considering a wide variety of synthetic and real-world graphs. The experimental evaluation shows that cracker consistently outperforms state-of-the-art approaches both in terms of total computation time and volume of messages exchanged.

In this paper, we propose a scheme to solve large dense graph problems under the MapReduce framework. The graph data is organized in terms of blocks and all blocks are assigned to different map workers for parallel processing. Intermediate results of map workers are combined by one reduce worker for the next round of processing. This procedure is iterative and the graph size can be reduced substantially after each round. In the last round, a small graph is processed on one single map worker to produce the final result. Specifically, we present some basic algorithms like Minimum Spanning Tree, Finding Connected Components and Single-Source Shortest Path which can be implemented efficiently using this scheme. We also offer a mathematical formulation to determine the parameters under our scheme so as to achieve the optimal running-time performance. Note that the proposed scheme can be applied in MapReduce-like platforms such as Spark. We use our own cluster and Amazon EC2 as the testbeds to respectively evaluate the performance of the proposed Minimum Spanning Tree algorithm under the MapReduce and Spark frameworks. The experimental results match well with our theoretical analysis. Using this approach, many parallelizable problems can be solved in MapReduce-like frameworks efficiently.

We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n2) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. l7r have been considered to be the most efficient on the LARPBS model till now. Their algorithm l7r for these two problems require O(log n) time and O(n3/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n2) processors. No previous algorithm was known for these latter problems on the LARPBS.

We present two new algorithms for finding the biconnected components of a large undirected sparse graph. The first algorithm is based on identifying articulation points and labeling edges using multiple connectivity queries, and the second approach uses the color propagation technique to decompose the graph. Both methods use a breadth-first spanning tree and some auxiliary information computed during Breadth-First Search (BFS). These methods are simpler than the Tarjan-Vishkin PRAM algorithm for biconnectivity and do not require Euler tour computation or any auxiliary graph construction. We identify steps in these algorithms that can be parallelized in a shared-memory environment and develop tuned OpenMP implementations. Using a collection of large-scale real-world graph instances, we show that these methods outperform the state-of-the-art Cong-Bader biconnected components implementation, which is based on the Tarjan-Vishkin algorithm. We achieve up to 7.1× and 4.2× parallel speedup over the serial Hopcroft-Tarjan and parallel Cong-Bader algorithms, respectively, on a 16-core Intel Sandy Bridge system. For some graph instances, due to the fast BFS-based preprocessing step, the single-threaded implementation of our first algorithm is faster than the serial Hopcroft-Tarjan algorithm.

Graph isomorphism (GI) is a fundamental problem that commonly appears in graph-based applications, such as pattern recognition and computer vision. This paper presents a tree search based method for the determination of GI. In the proposed method, all possible sequences of a source graph are represented as all paths on a tree, and compared with an arbitrary sequence of a destination graph by an evaluation function in terms of bijectivity. Experimental results show that the proposed method is more efficient than an existing solution especially for that given two graphs are isomorphic.

Large scale graph processing represents an interesting challenge due to the lack of locality. This paper presents Path Graph for improving iterative graph computation on graphs with billions of edges. Our system design has three unique features: First, we model a large graph using a collection of tree-based partitions and use an path-centric computation rather than vertex-centric or edge-centric computation. Our parallel computation model significantly improves the memory and disk locality for performing iterative computation algorithms. Second, we design a compact storage that further maximize sequential access and minimize random access on storage media. Third, we implement the path-centric computation model by using a scatter/gather programming model, which parallels the iterative computation at partition tree level and performs sequential updates for vertices in each partition tree. The experimental results show that the path-centric approach outperforms vertex centric and edge-centric systems on a number of graph algorithms for both in-memory and out-of-core graphs.

GraphLab, distributed graph-processing framework, has found multiple applications in data-mining. Its scalability makes it the perfect choice for running graph algorithms on large data. The current scheduler in GraphLab splits the graph based on various partitioning strategies. These strategies split the graph into approximately equal parts, which is suited for homogeneous clusters, but is liable to perform poorly in the presence of heterogeneity. A number of challenges arise when the nodes differ in memory and processing power. We show that memory in particular can be a severe bottleneck, even leading to the termination of certain jobs. We determine the extent to which the current scheduler can handle heterogeneity. We further propose GraphIVE (Graph Processing In Varied Environments), a capability-aware graph partitioning policy for GraphLab applications. Moreover, GraphIVE continously tries to reach optimum performance via hill climbing. We describe how GraphIVE reduces the communication overhead by reducing the replication factor of vertices. We implemented a prototype of GraphIVE and present the preliminary results. GraphIVE significantly improves the execution time of jobs. The results also show how it allows for seamless graph processing on a heterogeneous cluster.

Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. Most GA algorithms explore a search tree using the individualization-refinement procedure. Four novel techniques are proposed which increase the performance of any algorithm of this type by reducing the depth of the search tree and by effectively pruning it. We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of an input graph. Then, we describe how these techniques have been incorporated into the GA algorithm conauto, asconauto-2.03, with at most an additive polynomial increase in its asymptotic time complexity. Using a benchmark of different graph families, we have evaluated the impact of these techniques on the size of the search tree, observing a significant reduction both when they are applied individually and when all of them are applied together. This is also reflected in a reduction of the running time, which is substantial for some graph families. Finally, we have compared the search tree size of conauto-2.03 against those of other popular GA algorithms, observing that, in most cases, conauto explores less nodes than these algorithms.

Let f be a continuous function defined on a topological space. As we increase the function value, connected components in the level set of f appear, disappear, merge, or split, and the Reeb graph tracks these changes. The join and split trees of f track the changes of connected components in the sublevel and superlevel set respectively. If the Reeb graph is loop-free, then it is a tree called the contour tree. Given a piecewise linear function f defined on a simplicial complex K, Carr, Snoeyink and Axen proposed a simple and elegant algorithm to compute the contour tree of f by "merging" its join and split trees in near-linear time. In practice, there are often scenarios where one applies the algorithm of Carr et al. hoping to obtain a tree output, even if the Reeb graph of the input scalar field may have loops. This is particular common when handling high dimensional unorganized point clouds data. In this paper, we explore the validity of applying the algorithm of Carr et al. to any join and split tree and suggest modifications. We show that if the Reeb graph of f is not a tree, then the algorithm sometimes fails to produce a tree which reflects the input join and split trees. We introduce the concept of a JS-graph as a generalization of the contour tree. The JS-graph is a single graph which fully encodes the information in both join and split trees. A join tree, TJ, and split tree, TS, may have more than one JS-graph. We provide a characterization for all JS-graphs of TJ and TS. While the Reeb graph of f is a JS-graph, constructing the Reeb graph of f requires building and using the 2-skeleton of K. Our algorithm, based on the algorithm of Carr et al., constructs a JS-graph with at most 2(n−1) edges in O(n log2 n) time from just the join and split trees of K, where n is the number of vertices in K.

Current systems for graph computation require a distributed computing cluster to handle very large real-world problems, such as analysis on social networks or the web graph. While distributed computational resources have become more accessible developing distributed graph algorithms still remains challenging, especially to non-experts. In this work, we present GraphChi, a disk-based system for computing efficiently on graphs with billions of edges. By using a well-known method to break large graphs into small parts, and a novel Parallel Sliding Windows algorithm, GraphChi is able to execute several advanced data mining, graph mining and machine learning algorithms on very large graphs, using just a single consumer-level computer. We show, through experiments and theoretical analysis, that GraphChi performs well on both SSDs and rotational hard drives. We build on the basis of Parallel Sliding Windows to propose a new data structure Partitioned Adjacency Lists, which we use to design an online graph database GraphChi-DB.We demonstrate that, on a single PC, GraphChi-DB can process over one hundred thousand graph updates per second, while simultaneously performing computation. GraphChi-DB compares favorably to existing graph databases, particularly on data that is much larger than the available memory. We evaluate our work both experimentally and theoretically. Based on the Parallel Sliding Windows algorithm, we propose new I/O efficient algorithms for solving fundamental graph problems. We also propose a novel algorithm for simulating billions of random walks in parallel on a single computer. By repeating experiments reported for existing distributed systems we show that with only fraction of the resources, GraphChi can solve the same problems in a very reasonable time. Our work makes large-scale graph computation available to anyone with a modern PC.

A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for understanding call graph construction algorithms and an empirical comparison of a representative set of algorithms. We first present a general parameterized algorithm that encompasses many well-known and novel call graph construction algorithms. We have implemented this general algorithm in the Vortex compiler infrastructure, a mature, multilanguage, optimizing compiler. The Vortex implementation provides a "level playing field" for meaningful cross-algorithm performance comparisons. The costs and benefits of a number of call graph construction algorithms are empirically assessed by applying their Vortex implementation to a suite of sizeable (5,000 to 50,000 lines of code) Cecil and Java programs. For many of these applications, interprocedural analysis enabled substantial speed-ups over an already highly optimized baseline. Furthermore, a significant fraction of these speed-ups can be obtained through the use of a scalable, near-linear time call graph construction algorithm.

In data models that have graph representations, users navigate following the links of the graph structure. Conducting data mining on collected information about user accesses in such models, involves the determination of frequently occurring access sequences. In this paper, the problem of finding traversal patterns from such collections is examined. The determination of patterns is based on the graph structure of the model. For this purpose, three algorithms, one which is level-wise with respect to the lengths of the patterns and two which are not are presented. Additionally, we consider the fact that accesses within patterns may be interleaved with random accesses due to navigational purposes. The definition of the pattern type generalizes existing ones in order to take into account this fact. The performance of all algorithms and their sensitivity to several parameters is examined experimentally.

A fundamental problem of symbolic analysis of electric networks when using the signal-flow (SFG) graph method is to find the common tree of the current and voltage graph (G_I and G_V, respectively). In this paper we introduce a novel method in order to determine a common tree of both graphs, which may be used to obtain the symbolic network transfer function when carrying out the small-signal analysis of linear(ised) circuits.

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n·?(m,n)+m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and ?(m,n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k?1)-connected graph. For k=4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.

Depth-first search, as developed by Tarjan and coauthors, is a fundamental technique of efficient algorithm design for graphs [23]. This note presents depth-first search algorithms for two basic problems, strong and biconnected components. Previous algorithms either compute auxiliary quantities based on the depth-first search tree (e.g., LOWPOINT values) or require two passes. We present one-pass algorithms that only maintain a representation of the depth-first search path. This gives a simplified view of depth-first search without sacrificing efficiency. In greater detail, most depth-first search algorithms (e.g., [23,10,11]) compute so-called LOWPOINT values that are defined in terms of the depth-first search tree. Because of the success of this method LOWPOINT values have become almost synonymous with depth-first search. LOWPOINT values are regarded as crucial in the strong and biconnected component algorithms, e.g., [14, pp. 94, 514]. Tarjan’s LOWPOINT method for strong components is presented in texts [1, 7,14,16,17,21]. The strong component algorithm of Kosaraju and Sharir [22] is often viewed as conceptu

We solve a number of important and interesting problems from graph theory on a linear array with a reconfigurable pipelined optical bus system. Our algorithms are based on fast matrix multiplication and extreme value finding algorithms, and are currently the fastest algorithms. We also distinguish the two cases where weights have bounded/unbounded magnitude and precision.

When evaluating the survivability performance of a communication network, it is important to detect whether the graph is connected, whether there are separation nodes and separation pairs. The algorithms [ I ] and [2] developed by Tarjan and Hopcroft are the adequate tools for this purpose. They are able to determine the bi- and triconnected components of a graph in o(N+E) where N is the number of nodes and E the number of edges of the graph. Practically however, the decomposition of the graph is a step only in the evaluation of the connectivity performance of a graph. Indeed, when a separation element (node or pair) has been detected, it is crucial to know what are the consequences if this element fails down. For example, which precise parts of the graph are disconnected or more simply how large are the parts which are separated by this element'? The paper introduces the notion of rest-connectivity. Basically, for each separation element, the rest-connectivity value is defined as the number of node pairs which got disconnected by the failure of that separation element. In this paper, algorithms [1 ] and [2] are enhanced in order to determine the rest-connectivity values for all separation nodes and pairs of a graph while keeping the complexity in o(N+E).

Preserving the "mental map" is major goal of interactive graph drawing algorithms. Several models have been proposed for formalizing the notion of mental map. Additional work needs to be done to formulate and validate "difference" metrics which can be used in practice. This paper introduces a framework for defining and validating metrics to measure the difference between two drawings of the same graph.

This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of Ω( m 0 ) operations, where m 0 is the number of edges in the initial graph, the expected time for p updates is O ( p log 3 n ) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O (log n /log log n ). For the k -edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O ( p log 3 n ) and the expected time for q queries is O ( qk log 3 n ). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O ( pk log 3 n ). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O (( p log 3 n log U )/ε) for p updates, where the weights of the edges are between 1 and U .

This paper presents a procedure for automatically drawing directed graphs. Our system, Clan-based Graph Drawing Tool (CG), uses a unique clan-based graph decomposition to determine intrinsic substructures (clans) in the graph and to produce a parse tree. The tree is given attributes that specify the node layout. CG then uses tree properties with the addition of "routing nodes" to route the edges. The objective of the system is to provide, automatically, an aesthetically pleasing visual layout for arbitrary directed graphs. The prototype has shown the strengths of this approach. The innovative strategy of clan-based graph decomposition is the first digraph drawing technique to analyze locality in the graph in two dimensions. The typical approach to drawing digraphs uses a single dimension, level, to arrange the nodes.

Balanced graph partition is a type of graph partitioning problem that divides the given graph into components, such that the components are of about the same size and there are few connections between the components. The existing approaches partition the graph initially in a random manner which has a very high impact on determining the final quality of the solution. Recently, Multilevel Partitioning methods are proven to be faster among other approaches. This paper proposes a multilevel hybrid algorithm for balanced graph partitioning. Here graph is initially partitioned using Balanced Big method in order to improve the initial solution quality. Further, the quality of the obtained solution is improved using local search refinement procedure. The experimental results indicate that the relatively good initial partitions, when subjected to local search techniques like tabu search and hill climbing, results in better solutions. The experimental results also indicate that for the proposed approach, when the number of partitions increase (are high), the quality of the solution is better than the currently available solutions reported in the existing approaches.

The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which—given as input an n-vertex graph, a tree decomposition of width w, and an integer t—decides whether the input graph has treedepth at most t in time 2 O(wt) ·n. We use this to construct further algorithms which do not require a tree decomposition as part of their input: A simple algorithm which decides treedepth in linear time for a fixed t, thus answering an open question posed by Ossona de Mendez and Nesetřil as to whether such an algorithm exists, a fast algorithm with running time \(2^{O(t^2)} \cdot n\) and an algorithm for chordal graphs with running time 2 O(t logt)·n.

We study a broad class of graph partitioning problems, where each problem is specified by a graph \(G=(V,E)\), and parameters \(k\) and \(p\). We seek a subset \(U\subseteq V\) of size \(k\), such that \(\alpha _1m_1 + \alpha _2m_2\) is at most (or at least) \(p\), where \(\alpha _1,\alpha _2\in \mathbb {R}\) are constants defining the problem, and \(m_1, m_2\) are the cardinalities of the edge sets having both endpoints, and exactly one endpoint, in \(U\), respectively. This class of fixed-cardinality graph partitioning problems (FGPPs) encompasses Max \((k,n-k)\)-Cut, Min \(k\)-Vertex Cover, \(k\)-Densest Subgraph, and \(k\)-Sparsest Subgraph.

The World Wide Web structure can be represented by a directed graph named as the web graph. The web graphs have been used in a wide range of applications. However, the increasingly large-scale web graphs pose great challenges to the traditional memory-resident graph algorithms. In the literature, K 2-tree can efficiently compress the web graphs while supporting fast querying in the compressed data. Inspired by K 2-tree, we propose the Delta-K 2-tree compression approach, which exploits the characteristics of similarity between neighbor nodes in the web graphs. In addition, we design a node reordering algorithm to further improve the compression ratio. We compare our approach with the state-of-the-art algorithms, including K 2-tree, WebGraph, and AD. Experimental results of web graph compression on four datasets show that our Delta-K 2-tree approach outperforms the other three in compression ratio (1.66-2.55 bits per link), and meanwhile supports fast forward and reverse querying in graphs.

This paper presents a graph-based representation of success trees to evaluate the reliability of an embedded system. First, a success tree is constructed by deriving a characteristic function from a graph-based system model automatically. The constructed success tree is then translated to a graph (called a success graph) which supports both cyclic and acyclic data dependencies in applications to be mapped to the system resources and analyzed for reliability. To analyze the success graph, an algorithm called 0-propagation is introduced which propagates errors through the graph. The system fails if the errors propagate to the output of the success graph. Experimental results show that the proposed technique can simply and efficiently construct and analyze success trees of real-life embedded systems in a short time with negligible inaccuracy which suits well for evaluating the reliability of complex systems, e. g., as part of a design space exploration.

In this paper we present a linear time and space algorithm for constructing a visibility representation of a planar graph on an [Formula: see text] grid, thereby improving the previous bound of (2n-5)×(n-1). To this end we build in linear time the 4-block tree of a planar graph, which improves previous time bounds. Moreover, this is the first time that the technique of splitting a graph into its 4-connected components is used successfully in graph drawing

We are concerned with the issue of detecting changes of graph partitioning structures from a graph sequence. We call this issue GPCD(graph partitioning change detection). The graph partitioning structures may represent network communities. Hence GPCD is important in that it leads to discovery of important events which cause changes of network communities. We introduce a new algorithm for GPCD, denoted as TREE. The key ideas are: 1) we employ probabilistic trees to represent probabilistic models of graph partitioning structures. 2) We then reduce GPCD into the issue of detecting changes of trees on the basis of the minimum description length (MDL) principle. 3) By taking the cost of changes into consideration, we realize significantly less false alarm rates for change detection than the baseline method called Graph Scope. We empirically demonstrate that TREE is able to detect changes more accurately than Graph Scope.

Graph algorithms play a prominent role in several fields of sciences and engineering. Notable among them are graph traversal, finding the connected components of a graph, and computing shortest paths. There are several efficient implementations of the above problems on a variety of modern multiprocessor architectures. It can be noticed in recent times that the size of the graphs that correspond to real world data sets has been increasing. Parallelism offers only a limited succor to this situation as current parallel architectures have severe short-comings when deployed for most graph algorithms. At the same time, these graphs are also getting very sparse in nature. This calls for particular work efficient solutions aimed at processing large, sparse graphs on modern parallel architectures. In this paper, we introduce graph pruning as a technique that aims to reduce the size of the graph. Certain elements of the graph can be pruned depending on the nature of the computation. Once a solution is obtained for the pruned graph, the solution is extended to the entire graph. We apply the above technique on three fundamental graph algorithms: breadth first search (BFS), Connected Components (CC), and All Pairs Shortest Paths (APSP). To validate our technique, we implement our algorithms on a heterogeneous platform consisting of a multicore CPU and a GPU. On this platform, we achieve an average of 35% improvement compared to state-ofthe-art solutions. Such an improvement has the potential to speed up other applications that rely on these algorithms.

In many applications of graph algorithms, including communication networks, graphics, assembly planning, and VLSI design, graphs are subject to discrete changes, such as additions or deletions of edges or vertices. In the last decades there has been a growing interest in such dynamically changing graphs, and a whole body of algorithms and data structures for dynamic graphs has been discovered. This chapter is intended as an overview of this field. In a typical dynamicgraphproblemonewould like to answerqueries ongraphs that areundergoinga sequence of updates, for instance, insertions and deletions of edges and vertices. The goal of a dynamic graph algorithm is to update efficiently the solution of a problem after dynamic changes, rather than having to recompute it from scratch each time. Given their powerful versatility, it is not surprising that dynamic algorithms and dynamic data structures are often more difficult to design and analyze than their static counterparts. We can classify dynamic graph problems according to the types of updates allowed. A problemis said to be fully dynamic if the update operations include unrestricted insertions and deletions of edges. A problem is called partially dynamic if only one type of update, either insertions or deletions, is allowed. If only insertions are allowed, the problem is called incremental; if only deletions are allowed it is called decremental. In this chapter, we describe fully dynamic algorithms for graph problems. We present dynamicalgorithms for undirected graphs in Section 9.2. Dynamic algorithms for directed graphs are next described in Section 9.3. Finally, in Section 9.4 we describe some open problems.

The amount of graph-structured data has recently experienced an enormous growth in many applications. To transform such data into useful information, high-performance analytics algorithms and software tools are necessary. One common graph analytics kernel is community detection (or graph clustering). Despite extensive research on heuristic solvers for this task, only few parallel codes exist, although parallelism is often necessary to scale to the data volume of real-world applications. We address the deficit in computing capability by a flexible and extensible clustering algorithm framework with shared-memory parallelism. Within this framework we implement our parallel variations of known sequential algorithms and combine them by an ensemble approach. In extensive experiments driven by the algorithm engineering paradigm, we identify the most successful parameters and combinations of these algorithms. The processing rate of our fastest algorithm exceeds 10M edges/second for many large graphs, making it suitable for massive data streams. Moreover, the strongest algorithm we developed yields a very good tradeoff between quality and speed.

The breadth-first search (BFS) is one of the most important kernels in graph theory. The Graph500 benchmark measures the performance of any supercomputer performing a BFS in terms of traversed edges per second (TEPS). Previous studies have proposed hybrid approaches that combine a well-known top-down algorithm and an efficient bottom-up algorithm for large frontiers. This reduces some unnecessary searching of outgoing edges in the BFS traversal of a small-world graph, such as a Kronecker graph. In this paper, we describe a highly efficient BFS using column-wise partitioning of the adjacency list while carefully considering the non-uniform memory access (NUMA) architecture. We explicitly manage the way in which each working thread accesses a partial adjacency list in local memory during BFS traversal. Our implementation has achieved a processing rate of 11.15 billion edges per second on a 4-way Intel Xeon E5-4640 system for a scale-26 problem of a Kronecker graph with 226 vertices and 230 edges. Not all of the speedup techniques in this paper are limited to the NUMA architecture system. With our winning Green Graph500 submission of June 2013, we achieved 64.12 GTEPS per kilowatt hour on an ASUS Pad TF700T with an NVIDIA Tegra 3 mobile processor.

Balanced graph partitioning is a well known NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems including the optimal storage of large sets of graph-structured data over several hosts-A key problem in today's Cloud infrastructure. However, in very large-scale distributed scenarios, state-of-the-Art algorithms are not directly applicable, because they typically involve frequent global operations over the entire graph. In this paper, we propose a fully distributed algorithm, called JA-BE-JA, that uses local search and simulated annealing techniques for graph partitioning. The algorithm is massively parallel: there is no central coordination, each node is processed independently, and only the direct neighbors of the node, and a small subset of random nodes in the graph need to be known locally. Strict synchronization is not required. These features allow JA-BE-JA to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We perform a thorough experimental analysis, which shows that the minimal edge-cut value achieved by JA-BE-JA is comparable to state-of-the-Art centralized algorithms such as METIS. In particular, on large social networks JA-BEJA outperforms METIS, which makes JA-BE-JA-A bottom-up, self-organizing algorithm-A highly competitive practical solution for graph partitioning. QC 20131218

Graphs enjoy profound importance because of their versatility and expressivity. They can be effectively used to represent social networks, web search engines and genome sequencing. The field of graph pattern matching has been of significant importance and has wide-spread applications. Conceptually, we want to find subgraphs that match a pattern in a given graph. Much work has been done in this field with solutions like Subgraph Isomorphism and Regular Expression matching. With Big Data, scientists are frequently running into massive graphs that have amplified the challenge that this area poses. We study the speedup and communication behavior of three distributed algorithms for inexact graph pattern matching. We also study the impact of different graph partitionings on runtime and network I/O. Our extensive results show that the algorithms exhibit excellent scalable behavior and min-cut partitioning can lead to improved performance under some circumstances, and can drastically reduce the network traffic as well.

This work treats the problem of designing data-oblivious algorithms for classical and widely used graph problems. A data-oblivious algorithm is defined as having the same sequence of operations regardless of the input data and data-independent memory accesses. Such algorithms are suitable for secure processing in outsourced and similar environments, which serves as the main motivation for this work. We provide data-oblivious algorithms for breadth-first search, single-source single-destination shortest path, minimum spanning tree, and maximum flow, the asymptotic complexities of which are optimal, or close to optimal, for dense graphs.

There exist many graph-based applications including bioinformatics, social science, link analysis, citation analysis, and collaborative work. All need to deal with a large data graph. Given a large data graph, in this paper, we study finding top-k answers for a graph pattern query (kGPM), and in particular, we focus on top-k cyclic graph queries where a graph query is cyclic and can be complex. The capability of supporting kGPM provides much more flexibility for a user to search graphs. And the problem itself is challenging. In this paper, we propose a new framework of processing kGPM with on-the-fly ranked lists based on spanning trees of the cyclic graph query. We observe a multidimensional representation for using multiple ranked lists to answer a given kGPM query. Under this representation, we propose a cost model to estimate the least number of tree answers to be consumed in each ranked list for a given kGPM query. This leads to a query optimization approach for kGPM processing, and a top-k algorithm to process kGPM with the optimal query plan. We conducted extensive performance studies using a synthetic dataset and a real dataset, and we confirm the efficiency of our proposed approach.

This paper makes an efficient improvement of processor complexity while solving some connectivity problems on a reconfigurable meshes. We first derive two constant time algorithms in the proposed parallel processing system for computing the dominators and the dominator tree of an undirected graph either using a 3-D n×n×n processors or a 2-D n2×n2 processors, where n is the number of vertices of the graph. Then based on the dominator tree algorithm, we also solve many other graph connectivity problems in a constant time. They are the articulation points, bridges, biconnected components, and bridge-connected components problem in undirected graphs.

Fast parallel updating algorithms are proposed for the following problems: minimum-depth search for general graphs; depth-first search and breadth-depth search for directed acyclic graphs. The computational model used is a shared memory single-instruction stream, multiple-data stream computer that allows only the read conflict. The start-over algorithms for all these spanning tree problems are based on the “growing-by-doubling” paradigm and hence have a similar structure. It is shown that the same technique is equally effective in designing algorithms for certain updating problems with reference to the graph searching. The time complexity of all these updating algorithms are shown to be less than the corresponding start-over algorithms by a factor of log n.

The field of random graphs contains many surprising and interesting results. Here we demonstrate how some of these results can be used to develop stimulating, open-ended exercises for courses in algorithms and data structures or graph theory. Specifically, we provide problems for algorithms that compute minimum spanning trees, connected components, maximum flows, and all-pairs shortest paths.

Hopfield neural network model for finding the shortest path between two nodes in a graph was proposed recently in some literatures. In this paper, we present a modified version of Hopfield model to a more general problem of searching an optimal tree (least total cost tree) from a source node to a number of destination nodes in a graph. This problem is called Steiner tree in graph theory, where it is proved to be a NP-complete. Through computer simulations, it is shown that the proposed model could always find an optimal or near-optimal valid solution in various graphs.

Given a biconnected graph G with n vertices, m edges and a vertex r, the centering of a spanning tree problem asks for a spanning tree T of G with the given vertex r as center of T. In this paper we present an O(m) message complexity and O(n) time complexity distributed algorithm for centering a spanning tree of a biconnected graph.

An upward plane drawing of a directed acyclic graph is a plane drawing of the digraph in which each directed edge is represented as a curve monotone increasing in the vertical direction. Thomassen has given a nonalgorithmic, graph-theoretic characterization of those directed graphs with a single source that admit an upward plane drawing. This paper presents an efficient algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to find a representation of one such drawing. This result is made more significant in light of the recent proof by Garg and Tamassia that the problem is NP-complete for general digraphs. The algorithm decomposes the digraph into biconnected and triconnected components and defines conditions for merging the components into an upward plane drawing of the original digraph. To handle the triconnected components, we provide a linear algorithm to test whether a given plane drawing of a single-source digraph admits an upward plane drawing with the same faces and outer face, which also gives a simpler, algorithmic proof of Thomassen's result. The entire testing algorithm (for general single-source directed acyclic graphs) operates in $O(n^2)$ time and $O(n)$ space ($n$ being the number of vertices in the input digraph) and represents the first polynomial-time solution to the problem.