Search

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important special case by presenting an upper bound that matches the known log-space hardness [JKMT03]. In fact, we show the formally stronger result that planar graph canonization is in log-space. This improves the previously known upper bound of AC1 [MR91]. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to log-space reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in log-space by [DLN08]. This is achieved by using the above decomposition, and by making significant modifications to Lindell’s algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas, including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph. This lemma is crucial for the reduction to work in log-space.

Purpose The refined process structure tree (RPST), the hierarchy of non-overlapping single-entry single-exit (SESE) regions of a process model, has been utilized for better comprehension and more efficient analysis of business process models. Existing RPST methods, based on the triconnected components of edges, fail to identify a certain type of SESE region. The purpose of this paper is to introduce an alternative method for generating a complete RPST utilizing rather simple techniques. Design/methodology/approach The proposed method first focuses on the SESE regions of bonds and rigids, from the innermost ones to the outermost ones, utilizing dominance and post-dominance relations. Then, any SESE region of a series nested in a bond or a rigid is identified with a depth-first search variation. Two-phase algorithms and their completeness proofs, a software tool incorporating visualization of stepwise outcomes, and the experimental results of the proposed method are provided. Findings The proposed method utilizes simple techniques that allow their straightforward implementation. Visualization of stepwise outcomes helps process analysts to understand the proposed method and the SESE regions. Experiments with 604 SAP reference models demonstrated the limitation of the existing RPST methods. The proposed method, however, completely identified all types of SESE regions, defined with nodes, in less computation time than with the old methods. Originality/value Each triconnected component of the undirected version of a process model is associated with a pair of boundary nodes without discriminating between the entry and the exit. Here, each non-atomic SESE region is associated with two distinct entry and exit nodes from the original model in the form of a directed graph. By specifying the properties of SESE regions in more comprehensible ways, this paper facilitates a deeper understanding of SESE regions rather than relying on the resulting RPST.

Several well-studied classes of graphs admit structural characterizations via proper 2-cutsets which lead to polynomial-time recognition algorithms. The algorithms so far obtained for those recognition problems do not guarantee linear-time complexity. The bottleneck to those algorithms is the Ω ( n m ) -time complexity to fully decompose by proper 2-cutsets a graph with n vertices and m edges. In the present work, we investigate the 3-connected components of a graph and propose the use of the SPQR-tree data structure to obtain a fully decomposed graph in linear time. As a consequence, we show that the recognition of chordless graphs and of graphs that do not contain a propeller as a subgraph can be done in linear time, answering questions in the existing literature.

A cut tree is a combinatorial structure that represents the edge-connectivity between all pairs of vertices of an undirected graph. Cut trees solve the all pairs minimum s – t -cut problem efficiently. Cut trees have a large number of applications including the solution of important combinatorial problems in fields such as graph clustering and graph connectivity. They have also been applied to scheduling problems, social network analysis, biological data analysis, among others. Two sequential algorithms to compute a cut tree of a capacitated undirected graph are well known: the Gomory–Hu algorithm and the Gusfield algorithm. In this work three parallel cut tree algorithms are presented, including parallel versions of Gusfield and Gomory–Hu algorithms. A hybrid algorithm that combines techniques from both algorithms is proposed which provides a more robust performance for arbitrary instances. Experimental results show that the three algorithms achieve significant speedups on real and synthetic graphs. We discuss the trade-offs between the alternatives, each of which presents better results given the characteristics of the input graph. On several instances the hybrid algorithm outperformed both other algorithms, being faster than the parallel Gomory–Hu algorithm on most instances.

In this paper, we use a branch decomposition technique to improve approximations to the p-median problem. Starting from a support graph produced either by a combination of heuristics or by linear programming, we use dynamic programming guided by a branch decomposition of that support graph to find the best p-median solution on the support graph. Our results show that when heuristics are used to build the support graph and the support graph has branchwidth at most 7, our algorithm is able to provide a solution of lower cost than any of the heuristic solutions. When linear programming is used to build the support graph and the support graph has branchwidth at most 7, then our algorithm provides better solutions than popular heuristics and is faster than integer programming. Thus, our algorithm is a useful practical tool when support graphs have branchwidth at most 7.

This paper aims at bridging the two important trends in efficient graph cuts in the literature, the one is to decompose a graph into several smaller subgraphs to take the advantage of parallel computation, the other is to reuse the solution of the max-flow problem on a residual graph to boost the efficiency on another similar graph. Our proposed parallel dynamic graph cuts algorithm takes the advantages of both, and is extremely efficient for certain dynamically changing MRF models in computer vision. The performance of our proposed algorithm is validated on two typical dynamic graph cuts problems: the foreground-background segmentation in video, where similar graph cuts problems need to be solved in sequential and GrabCut, where graph cuts are used iteratively.

Automated graph-drawing systems utilize procedures to place vertices and arcs in order to produce graphs with desired properties. Incremental or dynamic procedures are those that preserve key characteristics when updating an existing drawing. These methods are particularly useful in areas such as planning and logistics, where updates are frequent. We propose a procedure based on the scatter search methodology that is adapted to the incremental drawing problem in hierarchical graphs. These drawings can be used to represent any acyclic graph. Comprehensive computational experiments are used to test the efficiency and effectiveness of the proposed procedure.

Analytical graph algorithms commonly compute metrics for a graph at one point in time. In practice it is often also of interest how metrics change over time, e.g., to find trends. For this purpose, algorithms must be executed for multiple graph snapshots. We present Single Algorithm Multiple Snapshots (SAMS) , a novel approach to execute algorithms concurrently for multiple graph snapshots. SAMS automatically transforms graph algorithms to leverage similarities between the analyzed graph snapshots. The automatic transformation interleaves algorithm executions on multiple snapshots, synergistically shares their graph accesses and traversals, and optimizes the algorithm's data layout. Thus, SAMS can amortize the cost of random data accesses and improve memory bandwidth utilization---two main cost factors in graph analytics. We extensively evaluate SAMS using six well-known algorithms and multiple synthetic as well as real-world graph datasets. Our measurements show that in multi-snapshot analyses, SAMS offers runtime improvements of up to two orders of magnitude over traditional snapshot-at-a-time execution.

We present a recursion scheme based on attribute grammars that can be transparently applied to trees and acyclic graphs. Our recursion scheme allows the programmer to implement a tree traversal or a tree transformation and then apply it to compact graph representations of trees instead. The resulting graph traversal or graph transformation avoids recomputation of intermediate results for shared nodes – even if intermediate results are used in different contexts. Consequently, this approach leads to asymptotic speedup proportional to the compression provided by the graph representation. In general, however, this sharing of intermediate results is not sound. Therefore, we complement our implementation of the recursion scheme with a number of correspondence theorems that ensure soundness for various classes of traversals. We illustrate the practical applicability of the implementation as well as the complementing theory with a number of examples.

The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characterization that is proved in more than twenty pages, Chudnovsky and Seymour [Combinatorica 2010] gave the previously only known polynomial-time algorithm, running in $O(mn^2)$ time, to solve the three-in-a-tree problem on an $n$-vertex $m$-edge graph. Their three-in-a-tree algorithm has become a critical subroutine in several state-of-the-art graph recognition and detection algorithms. In this paper we solve the three-in-a-tree problem in $\tilde{O}(m)$ time, leading to improved algorithms for recognizing perfect graphs and detecting thetas, pyramids, beetles, and odd and even holes. Our result is based on a new and more constructive characterization than that of Chudnovsky and Seymour. Our new characterization is stronger than the original, and our proof implies a new simpler proof for the original characterization. The improved characterization gains the first factor $n$ in speed. The remaining improvement is based on dynamic graph algorithms., 46 pages, 12 figures, accepted to STOC 2020

A graph is planar if it can be drawn or embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. A plane graph is a planar graph with a fixed planar embedding in the plane. A drawing problem X for a plane graph G asks to determine whether G has a drawing D satisfying a set P of given properties and to find D if it exists. The corresponding problem for a planar graph G asks to determine whether G has a planar embedding \(\varGamma \) such that \(\varGamma \) has a drawing D satisfying the set P of properties and find D if it exists. If every embedding of G has a drawing D satisfying P, then the problem is trivial, i.e., the problem for plane graphs and that for planar graphs are the same. Otherwise, the problem for planar graphs becomes difficult even if an efficient solution of the problem for a plane graph exists since a planar graph may have an exponential number of planar embeddings. Various techniques are found in literature that are used to solve the drawing problems for planar graphs. In this paper we review three of the widely used techniques, namely, (i) reduction to planarity testing, (ii) incremental modification and (iii) SPQR-tree decomposition.

Locally-biased graph algorithms are algorithms that attempt to find local or small-scale structure in a large data graph. In some cases, this can be accomplished by adding some sort of locality constraint and calling a traditional graph algorithm; but more interesting are locally-biased graph algorithms that compute answers by running a procedure that does not even look at most of the input graph. This corresponds more closely to what practitioners from various data science domains do, but it does not correspond well with the way that algorithmic and statistical theory is typically formulated. Recent work from several research communities has focused on developing locally-biased graph algorithms that come with strong complementary algorithmic and statistical theory and that are useful in practice in downstream data science applications. We provide a review and overview of this work, highlighting commonalities between seemingly-different approaches, and highlighting promising directions for future work., Comment: 19 pages, 13 figures

Graph processing is becoming a crucial component for analyzing big data arising in many application domains such as social and biological networks, fraud detection, and sentiment analysis. As a result, a number of computational models for graph analytics have been proposed in the literature to help users write efficient large scale graph algorithms. In this paper we present an alternative model for implementing graph algorithms using a linear algebra based specification. We first specify a set of linear algebra primitives that allows users to express graph algorithms by composition of linear algebra operations. We then describe a high performance implementation of these primitives using C $$++$$ and subsequently its integration with the Spark framework to achieve the scalability we need for large systems. We provide an overview of our implementation and also compare and contrast the expressiveness and performance of various algorithms implemented with our approach with that of the current Spark GraphX implementation of those algorithms.

Large scale iterative graph computation presents an interesting systems challenge due to two well known problems: (1) the lack of access locality and (2) the lack of storage efficiency. This paper presents PathGraph, a system for improving iterative graph computation on graphs with billions of edges. First, we improve the memory and disk access locality for iterative computation algorithms on large graphs by modeling a large graph using a collection of tree-based partitions. This enables us to use path-centric computation rather than vertex-centric or edge-centric computation. For each tree partition, we re-label vertices using DFS in order to preserve consistency between the order of vertex ids and vertex order in the paths. Second, a compact storage that is optimized for iterative graph parallel computation is developed in the PathGraph system. Concretely, we employ delta-compression and store tree-based partitions in a DFS order. By clustering highly correlated paths together as tree based partitions, we maximize sequential access and minimize random access on storage media. Third but not the least, our path-centric computation model is implemented using a scatter/gather programming model. We parallel the iterative computation at partition tree level and perform sequential local updates for vertices in each tree partition to improve the convergence speed. To provide well balanced workloads among parallel threads at tree partition level, we introduce the concept of multiple stealing points based task queue to allow work stealings from multiple points in the task queue. We evaluate the effectiveness of PathGraph by comparing with recent representative graph processing systems such as GraphChi and X-Stream etc. Our experimental results show that our approach outperforms the two systems on a number of graph algorithms for both in-memory and out-of-core graphs. While our approach achieves better data balance and load balance, it also shows better speedup than the two systems with the growth of threads.

Recently graph has been drawing lots of attention both as a natural data model that captures fine-grained relationships between data entities and as a tool for powerful data analysis that considers such relationships. In this paper, we present a new graph database system that integrates a robust graph storage with an efficient graph analytics engine. Primarily, our system adopts two domain-specific languages (DSLs), one for describing graph analysis algorithms and the other for graph pattern matching queries. Compared to the API-based approaches in conventional graph processing systems, the DSL-based approach provides users with more flexible and intuitive ways of expressing algorithms and queries. Moreover, the DSL-based approach has significant performance benefits as well, (1) by skipping (remote) API invocation overhead and (2) by applying high-level optimization from the compiler.

With the popularity of social network, the demand for real-time processing of graph data is increasing. However, most of the existing graph systems adopt a batch processing mode, therefore the overhead of maintaining and processing of dynamic graph is significantly high. In this paper, we design iGraph, an incremental graph processing system for dynamic graph with its continuous updates. The contributions of iGraph include: 1) a hash-based graph partition strategy to enable fine-grained graph updates; 2) a vertexbased graph computing model to support incremental data processing; 3) detection and rebalance methods of hotspot to address the workload imbalance problem during incremental processing. Through the general-purpose API, iGraph can be used to implement various graph processing algorithms such as PageRank. We have implemented iGraph on Apache Spark, and experimental results show that for real life datasets, iGraph outperforms the original GraphX in respect of graph update and graph computation.

The SPQR-tree is a data structure that compactly represents all planar embeddings of a biconnected planar graph. It plays a key role in constrained planarity testing.

Presents method for modeling multiple situations of interest as single template graph.Enables precedence tree guidance of a graph matching (GM) search heuristic.Demonstrates significant speedup of the proposed AND/OR GM methodology.Performs numerous numerical experiments investigating other AND/OR GM policies.Describes intelligence analysis applications for the proposed techniques. Intelligence analysis is a domain characterized by a torrent of streaming data within which a very small portion contains useful knowledge or actionable intelligence. Intelligence analysts have to sift through the compiled data and weave through a complex web of convoluted connections in an attempt to illuminate information requirements (IR) and maintain situational awareness. Automated methodologies have eased the manual burden of this process to some extent. Data are naturally modeled in a graphical form representing the known people, places, events and the relationships between them. Graph matching algorithms in which an information requirement is formulated as a template graph or situation of interest to be found in the observed data graph have been successfully employed in intelligence analysis processes. Absent from these past contributions is the recognition that partial information requirements, such as indicators and warnings, are not mutually exclusive to a specific IR, and an understanding of the characteristics of the underlying data can lead to significant performance benefits. The knowledge of overlapping template sections forms the motivation for precedence tree guided search and AND/OR templates. Through the recognition of the overlapping sections, a single AND/OR template can be created to answer many information requirements. This paper presents a novel algorithm for the intelligent traversal of an AND/OR template, providing increased algorithmic efficiency over the execution of multiple sequential graph matching instances. This paper focuses on development of an algorithm for intelligent AND/OR template traversal with computational results illustrating the effectiveness of the developed methods. The results indicate a significant improvement in runtime (with a speedup over 5 in some cases) while maintaining a good solution quality (within 2% of multiple AND path graph matching executions) in AND/OR and precedence tree guided graph matching.

In this paper we design and implement an algorithm for finding the biconnected components of a given graph. Our algorithm is based on experimental evidence that finding the bridges of a graph is usually easier and faster in the parallel setting. We use this property to first decompose the graph into independent and maximal 2-edge-connected subgraphs. To identify the articulation points in these 2-edge connected subgraphs, we again convert this into a problem of finding the bridges on an auxiliary graph. It is interesting to note that during the conversion process, the size of the graph may increase. However, we show that this small increase in size and the run time is offset by the consideration that finding bridges is easier in a parallel setting. We implement our algorithm on an Intel i7 980X CPU running 12 threads. We show that our algorithm is on average 2.45x faster than the best known current algorithms implemented on the same platform. Finally, we extend our approach to dense graphs by applying the sparsification technique suggested by Cong and Bader in [7].Â

We propose the use of SPQR-trees as a data structure to encode the 3-connected components of a graph and to obtain linear-time recognition algorithms for graph classes structurally characterized by 2-cutset decompositions.

Based on solid theoretical foundations, we present strong evidence that a number of real-world networks, taken from different domains such as Internet measurements, biological data, web graphs, and social and collaboration networks exhibit tree-like structures from a metric point of view. We investigate a few graph parameters, namely, the tree-distortion and the tree-stretch, the tree-length and the tree-breadth, Gromov's hyperbolicity, the cluster-diameter and the cluster-radius in a layering partition of a graph; such parameters capture and quantify this phenomenon of being metrically close to a tree. By bringing all those parameters together, we provide efficient means for detecting such metric tree-like structures in large-scale networks. We also show how such structures can be used. For example, they are helpful in efficient and compact encoding of approximate distance and almost shortest path information and in quick and accurate estimation of diameters and radii of those networks. Estimating the diameter and estimating the radius of a graph or distances between arbitrary vertices are fundamental primitives in many network and graph mining algorithms. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 671, 49-68 2016

We propose faster algorithms for the maximum flow problem and related problems based on graph decomposition. Our algorithms first construct indices (data structures) from a given graph, then use them for solving the problems. A basic problem is an all pairs maximum flow problem, which consists of two stages. In a preprocessing stage we construct an index, and in a query stage we process the query using the index. We can solve all pairs maximum flow problem and minimum cut problem using the indices. Time complexities of our algorithms depend on the size of the maximum triconnected component in the graph, say r. Our algorithms run faster than known algorithms if r is small. The maximum flow problem can be solved in \(\mathcal {O}(nr)\) time, which is faster than the best known \(\mathcal {O}(nm)\) algorithm [Orlin 2013] if \(r = o(m)\), where n and m are the numbers of vertices and edges, respectively.

Breadth-First Search (BFS) is a core primitive for graph traversal and a basis for many higher-level graph analysis algorithms. It is also representative of a class of parallel computations whose memory accesses and work distribution are both irregular and data dependent. Recent work has demonstrated the plausibility of GPU sparse graph traversal, but has tended to focus on asymptotically inefficient algorithms that perform poorly on graphs with nontrivial diameter. We present a BFS parallelization focused on fine-grained task management constructed from efficient prefix sum computations that achieves an asymptotically optimal O(|V| + |E|) gd work complexity. Our implementation delivers excellent performance on diverse graphs, achieving traversal rates in excess of 3.3 billion and 8.3 billion traversed edges per second using single- and quad-GPU configurations, respectively. This level of performance is several times faster than state-of-the-art implementations on both CPU and GPU platforms.

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 datasets 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 solution strategies 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 on the pruned graph, the solution is extended to the entire graph. Towards, this end we investigate pruning based on two strategies that justifies their use in current real world graphs.We apply the above technique on three fundamental graph algorithms: breadth first search (BFS), Connected Components (CC), and All Pairs Shortest Paths (APSP). For experimentations, we use three different sources for real world graphs. 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-of-the-art solutions. Such an improvement has the potential to speed up other applications reliant on these algorithms. Processing real world graphs in an efficient manner through input pruning.Two different pruning strategies based on 1-degree nodes and articulation points.Improvements upto 35% or 1.57x over current best known results.Experimental evaluation of algorithms proposed on several real world graphs.Heterogeneous multicore implementation provides better performance efficiency.

Visualizing the group structure of graphs is important in analyzing complex networks. The group structure referred to here includes not only community structures defined in terms of modularity and the like but also group divisions based on node attributes. Group-In-a-Box (GIB) is a graph-drawing method designed for visualizing the group structure of graphs. Using a GIB layout, it is possible to simultaneously visualize group sizes and both within-group and between-group structures. However, conventional GIB layouts do not optimize display of between-group relations, causing many long edges to appear in the graph area and potentially reducing graph readability. This paper focuses on the tree structure of treemap used in GIB layouts as a basis for proposing a tree-reordered GIB (TRGIB) layout with a procedure for replacing sibling nodes in the tree structure. Group proximity is defined in terms of between-group distances and connection weights, and an optimal tree reordering problem (OTRP) that minimizes group proximity is formulated as a mixed-integer linear programming (MILP) problem. Through computational experiments, we show that optimal layout generation is possible in practical time by solving the OTRP using a general mathematical programming solver.

In recent years, there has been renewed interest in casting graph algorithms in the language of linear algebra. By replacing the computations with appropriate operations over different semi-rings, different graph algorithms can be cast as a sequence of linear algebra operations. In this paper, we show that this recent trend allows us to leverage the Formal Linear Algebra Methods Environment (FLAME) methodology to formally specify, derive and implement a family of graph algorithms for counting the number of triangles (3-cliques) in a graph. In addition, we introduce a new back-end for the FLAME Application Programming Interface (API) that computes over sparse matrices stored in the compressed sparse row (CSR) format so that the correctness of the derived algorithm can be translated to the implementation.

Trees and graphs are two data structures that are commonly used in representing different kinds of data. They also have many associated algorithms taught in different courses. It is thus beneficial to have a tool that could be used by students, teachers and programmers to visually trace how their algorithms work. The work in this paper presents, CHR-Graph, an easy-to-use platform for animating trees and graphs and their correlated algorithms using Constraint Handling Rules (CHR).

We present a new multi-level graph drawing algorithm based on the k-core coarsening, a well-known cohesive subgroup analysis method in social network analysis. The k-core of a graph is also known as the degeneracy in graph theory, and can be computed in linear time. Our k-core based multi-level algorithm also includes a new concentric circle placement and a variation of force-directed layout to display the structure of graphs effectively. Experiments with real-world networks suggest that our algorithm performs well for visualization of large and complex scale-free networks, with a power-law degree distribution, a short diameter and a high clustering coefficient. Comparison with other multi-level algorithms shows that our method is fast and effective, in particular performs better than Walshaw [26] and FM3 [15].

The decomposition tree of a biconnected graph is in brief the decomposition tree of a biconnected graph by the set of all single cutsets of it (i.e., 2-vertex cutsets that are independent with all other 2-vertex cutsets). It is shown that this tree has much in common with the classical tree of blocks and cutpoints of a connected graph. With the help of the decomposition tree of a biconnected graph, a planarity criterion is proved and some upper bounds on the chromatic number of this graph are found. Finally, the structure of critical biconnected graphs is studied, and it is proved that each such graph has at least four vertices of degree 2. Bibliography: 11 titles.

Graphs are used to model complex data objects and their relationships in the real world. Finding occurrences of graph patterns in large graphs is one of the fundamental graph analysis tools used to discover underlying characteristics from these complex networks. In this paper, we propose a new tree-based approach for improving subgraph-matching performance. First, we introduce a new graph indexing mechanism known as Neighborhood Trees (NTree), which records the neighborhood relationships of each vertex in the large graph to filter negative vertices. Second, we decompose a query graph into a set of neighborhood trees and only a subset of candidate trees, which can properly recover the original query graph. In this way, the tree-at-a-time method is used to obtain the matched graphs. Third, we employ a graph query optimizer to determine the neighborhood tree selection order on the basis of the cost evaluation of tree join operations. Experiments on both real and synthetic databases demonstrate that our approach is more efficient than other state-of-the-art indexing methods.

Given an undirected, connected, edge-weighted graph, the dominating tree problem (DTP) seeks on this graph a tree of minimum weight such that each node of the graph either belongs to the tree or is adjacent to a node in the tree. This problem is $${\fancyscript{NP}}$$NP-hard. In this paper, we present an evolutionary algorithm with guided mutation (EA/G) to solve the DTP. This problem has several practical applications in the field of wireless sensor networks. EA/G is a recently proposed evolutionary algorithm that tries to overcome the shortcomings of genetic algorithms (GAs) and estimation of distribution algorithms both, and has the characteristics of both. We have compared the performance of our proposed approach with the state-of-the-art approaches presented in the literature. Computational results show the superiority of our approach in terms of solution quality as well as execution time.

Branch-and-price algorithms for the graph coloring problem use an exponentially sized independent set-based integer programming formulation to produce usually tight lower bounds to enable more aggressive pruning in the branch-and-bound tree. One major problem inherent to any branch-and-price scheme for graph coloring is that to avoid destroying the pricing problem structure during column generation, difficult-to-implement branching rules that modify the underlying graph must be used. This paper proposes an alternative branching strategy that does not change the graph to solve the pricing problem but rather modifies the search tree to require fewer calls to difficult instances of the pricing problem. This approach, called wide branching, generates many subproblems at each node in the branch-and-price tree; this significantly reduces the length of any path through the search tree. In contrast, traditional deep branching only creates two subproblems per node, assigning a variable to either 0 or 1. A delayed branching procedure is introduced that prevents the branching factor at any particular node from growing too large in this scheme. Finally, computational results are presented that show the wide branching strategy to be competitive with state-of-the-art graph coloring solvers.

We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire details. We present a user study to test the effectiveness of our approach. Furthermore, we performed an experimental analysis on popular force-directed graph drawing algorithms, in order to evaluate what is the algorithm that produces the smallest number of layers and if there is any correlation between the number of crossings and the number of layers of a graph layout. The proposed approach is useful to explore graph layouts, as confirmed by the presented user study. Furthermore, interesting considerations arise from the experimental evaluation, in particular, our results suggest that the number of layers of a graph layout may represent a reliable measure of its visual complexity. The algorithms presented in this paper can be effectively applied to graph layouts with a few hundreds of edges and vertices. For larger drawings that contain lots of crossings, the time complexity of our algorithms grows quadratically in the number of edges and more efficient techniques need to be devised. The proposed approach takes as input a layout produced by any graph drawing algorithm, therefore it can be applied in a variety of application domains. Several research directions can be explored to extend our framework and to devise new visualization paradigms to effectively present stratified drawings.

This paper presents a methodology for the description and finite-position dimensional synthesis of articulated systems with multiple end-effectors. The articulated system is represented as a rooted tree graph. Graph and dimensional synthesis theories are applied to determine when exact finite-position synthesis can be performed on the tree structures by considering the motion for all the possible subgraphs. Several examples of tree topologies are presented and synthesized. This theory has an immediate application on the design of novel multi-fingered hands. © 2013 Elsevier Ltd., This work is supported by the National Science Foundation under Grant No. 1208385.

Linkage learning in evolutionary algorithms is identifying the structure of the dependencies between variables of a problem in order to find the optimum solution of the problem. It is a necessary process for optimizing the hard problems that can not be optimized randomly via common recombination operators of simple genetic algorithm. This paper presents a simple yet effective linkage learner that works based on graph theory. A graph is used as the structure to keep the pairwise dependencies between variables of the problem. We call this graph 'the underlying dependency graph of the problem' UDGP. Maximum spanning tree MST of the UDGP is then found. It is shown that MST contains all the necessary linkages if the dependency graph is built upon sufficient population. In this approach, pairwise dependencies that are mutual information between each pair of variables, are used to find linkage information. The proposed approach has the advantage of being capable of learning the linkage without the need for the costly fit-to-data evaluations of model search. It is parameter free and the algorithm description is straight forward. The proposed technique is tested on several benchmark problems and it is shown to be able to compete with similar approaches. Based on the experimental results it can successfully find the linkage groups in a polynomial number of fitness evaluations.

The usage of graphs in the analysis and design of complex large-scale system structures, which require a significant computing capacity, has led to the need to seek for the new methods both of graph models representation and of graph operations implementation. To reduce the execution time of algorithms the parallel computing systems are appropriate to use.In this case, to achieve the maximum acceleration graph processing is implemented in hardware and software parts of the system. In the article, analysis of graph model operations was performed in the context of their implementation in a parallel computing system based on the abstract description of the graph by the sets that allows the utilizing of various parallel processing systems, regardless of their architecture features. The most common in the algorithms graph transformation operations were considered.As a result of analysis a set of elementary operations on graph structures, which constitute graph operations, was revealed, and graph operations parallel algorithms were realized. Efficiency evaluation of parallel algorithms, presented by speedup for each operation, showed a high degree of graph processing acceleration, compared with sequential operations algorithms.The proposed realization can be used to solve time-consuming large-scale tasks on parallel computing systems. At the same time, in a particular parallel processing system it is also possible to parallelize elementary operations thereby greatly reducing the execution time of operation in general.Further research is focused on describing and complementing current implementation with complex parallel graph transformation operations such as intersection, union, composition of graphs, etc., as well as analysis operations of various graph characteristics. That will expand the set of elementary operations and will provide an opportunity to evaluate more accurately the efficiency of parallel computing systems for processing graph models.

In this paper a new approximation algorithm for calculating the min-cut tree of an undirected edgeweighted graph has been proposed. This algorithm runs in

Image segmentation is a fundamental problem in computer vision. Despite many years of research, general purpose image segmentation is still a very challenging task because segmentation is inherently ill-posed. Among different segmentation schemes, graph theoretical ones have several good features in practical applications. It explicitly organizes the image elements into mathematically sound structures, and makes the formulation of the problem more flexible and the computation more efficient. In this paper, we conduct a systematic survey of graph theoretical methods for image segmentation, where the problem is modeled in terms of partitioning a graph into several sub-graphs such that each of them represents a meaningful object of interest in the image. These methods are categorized into five classes under a uniform notation: the minimal spanning tree based methods, graph cut based methods with cost functions, graph cut based methods on Markov random field models, the shortest path based methods and the other methods that do not belong to any of these classes. We present motivations and detailed technical descriptions for each category of methods. The quantitative evaluation is carried by using five indices - Probabilistic Rand (PR) index, Normalized Probabilistic Rand (NPR) index, Variation of Information (VI), Global Consistency Error (GCE) and Boundary Displacement Error (BDE) - on some representative automatic and interactive segmentation methods.

Graph models of social information systems typically contain trillions of edges. Such big graphs cannot be processed on a single machine. The graph object must be partitioned and distributed among machines and processed in parallel on a computer cluster. Programming such systems is very challenging. In this work, we present DH-Falcon, a graph DSL (domain-specific language) which can be used to implement parallel algorithms for large-scale graphs, targeting Distributed Heterogeneous (CPU and GPU) clusters. DH-Falcon compiler is built on top of the Falcon compiler, which targets single node devices with CPU and multiple GPUs. An important facility provided by DH-Falcon is that it supports mutation of graph objects, which allows programmer to write dynamic graph algorithms. Experimental evaluation shows that DH-Falcon matches or outperforms state-of-theart frameworks and gains a speedup of up to 13x.

Product shipping information is the related information of an ordered product that ready to be shipped to the foreign customer’s company, where the information represents as an irrefutable proof in black and white to the local manufacturer by E-mails. This messy and unordered list of information is stored in E-mail folders by the people incharge, which do not function in collating the information properly. So, in this paper, an algorithm is proposed on how to rearrange the messy information from the sequence of a path graph structure into a concise version of a caterpillar graph with achieving the concept of graceful labeling. The final graceful caterpillar graph consists of the full listed information together with the numbering, which able to assist people get the information fleetly for shipping arrangement procedure.

Given a graph [math] , the tree cover number of the graph, denoted [math] , is the minimum number of vertex disjoint simple trees occurring as induced subgraphs that cover all the vertices of G. This graph parameter was introduced in 2011 as a tool for studying the maximum positive semidefinite nullity of a graph, and little is known about it. It is conjectured that the tree cover number of a graph is at most the maximum positive semidefinite nullity of the graph. ¶ In this paper, we establish bounds on the tree cover number of a graph, characterize when an edge is required to be in some tree of a minimum tree cover, and show that the tree cover number of the [math] -dimensional hypercube is 2 for all [math] .